Pagini recente » Cod sursa (job #1680610) | Cod sursa (job #243055) | Cod sursa (job #2119426) | Cod sursa (job #2630504) | Cod sursa (job #2438307)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s1[2000001],s2[2000001];
int main()
{
long long n=1,m=1,i,k,poz,s=0,j=0;
f>>s2+1>>s1+1;
while(s1[n]!=0)
{
n++;
}
while(s2[m]!=0)
{
m++;
}
n--;
m--;
if(m>n)
{
g<<"0";
return 0;
}
long l[m+1],aux[1001];
/*Prefix*/
l[1]=0;
for(poz=2;poz<=m;poz++)
{
k=l[poz-1];
while((k>0)&&(s2[k+1]!=s2[poz]))
{
k=l[k];
}
if(s2[k+1]==s2[poz])
{
k=k+1;
}
l[poz]=k;
}
/*KMP*/
k=0;
for(poz=1;poz<=n;poz++)
{
while((k>0)&&(s2[k+1]!=s1[poz]))
{
k=l[k];
}
if(s2[k+1]==s1[poz])
{
k++;
}
if(k==m)
{
j++;
if(j<=1000)
{
aux[j]=poz-k;
k=l[k];
}
}
}
g<<j<<"\n";
if(j>1000)
{
s=1000;
}
else
{
s=j;
}
for(i=1;i<=s;i++)
{
g<<aux[i]<<" ";
}
return 0;
}