Pagini recente » Cod sursa (job #2882248) | Cod sursa (job #2902278) | Cod sursa (job #667498) | Cod sursa (job #2372618) | Cod sursa (job #651816)
Cod sursa(job #651816)
#include<fstream>
#define NMAX 2000100
using namespace std;
char A[NMAX],B[NMAX];
int n,m,nr,fail[NMAX],sol[1024];
void KMP() {
int i,q=0;
for(i=1;i<=m;i++) {
while(q && A[q+1] != B[i])
q=fail[q];
if(A[q+1] == B[i])
q++;
if(q==n) {
q=fail[n];
sol[nr++]=i-n;
if(nr==1000)
return;
}
}
}
void prefix() {
int i,q=0;
fail[1]=0;
for(i=2;i<=n;i++) {
while(q && A[q+1] != A[i])
q=fail[q];
if(A[q+1] == A[i])
q++;
fail[i]=q;
}
}
void citire() {
ifstream in("strmatch.in");
in.getline(A+1,NMAX);
in.getline(B+1,NMAX);
n=strlen(A+1);
m=strlen(B+1);
in.close();
}
void afis() {
int i;
ofstream out("strmatch.out");
out<<nr<<'\n';
for(i=0;i<nr;i++)
out<<sol[i]<<' ';
out<<' ';
out.close();
}
int main() {
citire();
prefix();
KMP();
afis();
}