Pagini recente » Cod sursa (job #2066367) | Cod sursa (job #2840870) | Cod sursa (job #188295) | Cod sursa (job #2931395) | Cod sursa (job #1230605)
#include <fstream>
#include <iostream>
#include <cstring>
#define nmax 2000001
using namespace std;
char A[nmax],B[nmax];
int pi[nmax],n,m,nr,poz[nmax];
void prefix(){
int i,q=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;
}
pi[1]=0;
}
int main(){
int q=0,i;
ifstream fin("strmatch.in");
fin>>A+1>>B+1;
fin.close();
n=strlen(A+1);
m = strlen(B+1);
prefix();
for(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){
nr++;
q = pi[q];
poz[nr] = i-n;
}
}
ofstream fout("strmatch.out");
fout << nr<<'\n';
if(nr > 1000) nr = 1000;
for(i=1;i<=nr;i++) fout << poz[i]<<' ';
fout << '\n';
fout.close();
return 0;
}