Pagini recente » Cod sursa (job #2548699) | Cod sursa (job #1896121) | Cod sursa (job #2407208) | Cod sursa (job #1848296) | Cod sursa (job #651817)
Cod sursa(job #651817)
#include<fstream>
#define NMAX 2000100
using namespace std;
char A[NMAX],B[NMAX];
int n,nr,fail[NMAX],sol[1024];
void KMP() {
int i,q=0;
for(i=1;B[i];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;A[i];i++) {
while(q && A[q+1] != A[i])
q=fail[q];
if(A[q+1] == A[i])
q++;
fail[i]=q;
}
n=i-1;
}
void citire() {
ifstream in("strmatch.in");
in.getline(A+1,NMAX);
in.getline(B+1,NMAX);
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();
}