Pagini recente » Cod sursa (job #364465) | Cod sursa (job #3284158) | Cod sursa (job #2510315) | Cod sursa (job #2755344) | Cod sursa (job #651822)
Cod sursa(job #651822)
#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;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];
nr++;
if(nr<1001)
sol[nr]=i-n;
}
}
m=i;
}
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,p;
ofstream out("strmatch.out");
out<<nr<<'\n';
p=min(1000,nr);
for(i=1;i<=p;i++)
out<<sol[i]<<' ';
out<<' ';
out.close();
}
int main() {
citire();
prefix();
KMP();
afis();
}