Pagini recente » Cod sursa (job #644299) | Cod sursa (job #1432146) | Cod sursa (job #1936779) | Cod sursa (job #1032232) | Cod sursa (job #856749)
Cod sursa(job #856749)
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
vector<int> sol;
char s1[2000005],s2[2000005];
int p[2000005];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int n,m,i;
gets(s1+1);gets(s2+1);
n=strlen(s1+1);m=strlen(s2+1);
int k;
/* prefixe: */
k=0;p[1]=0;
for(i=2;i<=n;i++)
{
while(k>0 && s1[k+1]!=s1[i])
k=p[k];
if(s1[k+1]==s1[i]) k++;
p[i]=k;
}
/* KMP: */
k=0;
for(i=1;i<=m;i++)
{
while(k>0 && s1[k+1]!=s2[i])
k=p[k];
if(s1[k+1]==s2[i])
k++;
if(k==n)
sol.push_back(i-1);
}
printf("%d\n",(int)sol.size());
for(i=0;i<min((int)sol.size(),1000);i++)
printf("%d ",sol[i]-n+1);
return 0;
}