Pagini recente » Cod sursa (job #2022513) | Cod sursa (job #1944377) | Cod sursa (job #2535208) | Cod sursa (job #2555907) | Cod sursa (job #952074)
Cod sursa(job #952074)
// KMP
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int NMAX = 2000005;
int Pi[NMAX],i,N,M,Cnt;
char A[NMAX],B[NMAX];
vector<int> Sol;
vector<int>::iterator it;
void Prefix()
{
Pi[1]=0; int 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;
}
}
void KMP()
{
int q=0;
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)
{
Cnt++;
if(Cnt<=1000) Sol.push_back(i-N);
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",A+1,B+1);
N=strlen(A+1); M=strlen(B+1);
Prefix(); KMP();
printf("%d\n",Cnt);
for(it=Sol.begin();it!=Sol.end();it++) printf("%d ",*it);
return 0;
}