Pagini recente » Cod sursa (job #865673) | Cod sursa (job #3198602) | Cod sursa (job #2682911) | Rating Reti Eniko (reti_eni) | Cod sursa (job #2335196)
#include <iostream>
#include <fstream>
using namespace std;
const int Maxx=2e6+1;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m;
int ans[Maxx];
int pi[Maxx];
string A,B;
void prefix(){
int i,q=0;
pi[1]=0;
for (i=2;i<=n;++i){
while (q && A[q+1]!=A[i]){
q=pi[q];
}
if (A[q+1]==A[i]){
++q;
}
pi[i]=q;
}
}
int main() {
fin>>A>>B;
n=A.size();
m=B.size();
A.insert(0," ");
B.insert(0," ");
prefix();
int q=0;
int sol=0;
for (int i=1;i<=m;++i){
while (q && A[q+1]!=B[i]){
q=pi[q];
}
if (A[q+1]==B[i]){
++q;
}
if (q==n) {
ans[++sol]=i-n;
}
}
fout<<sol<<"\n";
for (int i=1;i<=min(sol,1000);++i){
fout<<ans[i]<<" ";
}
return 0;
}