Pagini recente » Cod sursa (job #1465171) | Cod sursa (job #167664) | Istoria paginii runda/calalot1/clasament | Cod sursa (job #2448456) | Cod sursa (job #2866284)
#include<bits/stdc++.h>
#define SIZE 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char x[SIZE],y[SIZE];
int l[SIZE],sol[SIZE],nr,n,m;
void prefix()
{
int k=0,i;
for(i=2;i<=n;i++)
{
k=l[i-1];
while(k>0 && x[i]!=x[k+1])
{
k=l[k];
}
if(x[i]==x[k+1])k++;
l[i]=k;
}
}
void kmp()
{
int k=0,i;
for(i=1;i<=m;i++)
{
while(k>0 && y[i]!=x[k+1])
{
k=l[k];
}
if(y[i]==x[k+1])k++;
if(k==n)sol[++nr]=i-n;
}
g<<nr<<'\n';
for(i=1;i<=min(nr,1000);i++)
g<<sol[i]<<' ';
}
int main()
{
f.getline(x+1,SIZE);
f.getline(y+1,SIZE);
n=strlen(x+1);
m=strlen(y+1);
prefix();
kmp();
return 0;
}