Pagini recente » Cod sursa (job #110385) | Cod sursa (job #3274311) | Cod sursa (job #2534707) | Cod sursa (job #1955913) | Cod sursa (job #762250)
Cod sursa(job #762250)
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int N=2000010;
char a[N],s[N];
int prefix[N],rez[N];
void kmp()
{
int m=strlen(a+1),i,j;
prefix[0]=-1;
for (i=2;a[i];i++)
for (int j=prefix[i-1];j>=0;j=prefix[j])
if (a[j+1]==a[i])
{
prefix[i]=j+1;
break;
}
for (i=1, j=-1;s[i];i++)
for (j++;j>=0;j=prefix[j])
if (a[j+1]==s[i])
{
if (j==m-1)
rez[++rez[0]]=i-m;
break;
}
}
int main()
{
in>>a+1>>s+1;
kmp();
out<<rez[0]<<"\n";
rez[0]=min(rez[0],1000);
for (int i=1;i<=rez[0];i++)
out<<rez[i]<<" ";
out<<"\n";
return 0;
}