Pagini recente » Cod sursa (job #1881982) | Cod sursa (job #63579) | Cod sursa (job #1426917) | Cod sursa (job #368068) | Cod sursa (job #2074391)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,v[2000002],k,ap[1001];
char s[2000002],c[2000002];
void prefix()
{
int i,j;
s[0]=' ';
n=strlen(s)-1;
v[0]=v[1]=1;
j=1;
for(i=2;i<=n;i++)
{
if(s[i]==s[j])
v[i]=++j;
else
{
j=v[j-1];
while(s[j]!=s[i] && j!=1)
j=v[j-1];
if(j==1 && s[i]!=s[j]) v[i]=1;
else
v[i]=++j;
}
}
}
void kmp()
{
int i,j;
c[0]=' ';
int m=strlen(c)-1;
j=1;
for(i=1;i<=m;i++)
{
if(c[i]==s[j])
{
if(j==n)
{
if(k<1000)
ap[++k]=i-n;
else k++;
j=v[j];
}
else
j++;
}
else if(j!=1)
{
j=v[j-1];
i--;
}
}
}
int main()
{
fin>>(s+1);
int i,j;
prefix();
fin>>(c+1);
kmp();
fout<<k<<'\n';
for(i=1;i<=k && i<=1000;i++)
fout<<ap[i]<<" ";
fout<<'\n';
/* for(i=1;i<=n;i++)
fout<<v[i]<<" ";*/
return 0;
}