Pagini recente » Cod sursa (job #2161927) | Cod sursa (job #1631838) | Cod sursa (job #2725233) | Cod sursa (job #2573522) | Cod sursa (job #2438300)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s1[10000001],s2[10000001];
int main()
{
int n=1,m=1,i,k,poz,s=0;
f>>s2+1>>s1+1;
int l[m+1],aux[1001],j=0;
while(s1[n]!=0)
{
n++;
}
while(s2[m]!=0)
{
m++;
}
n--;
m--;
if(m>n)
{
g<<"0";
return 0;
}
/*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)
{
poz=n;
}
else
{
aux[j]=poz-k;
k=l[k];
}
}
}
g<<j<<"\n";
for(i=1;i<=j;i++)
{
g<<aux[i]<<" ";
}
return 0;
}