Pagini recente » Cod sursa (job #2189059) | Cod sursa (job #656620) | Cod sursa (job #1213637) | Cod sursa (job #2782421) | Cod sursa (job #1880336)
#include <fstream>
#include <cstring>
using namespace std;
char s1[2000005],s2[2000005];
int n,m,i,j,k;
int pi[2000006],sol[2000005];
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>s1;
f>>s2;
n=strlen(s1);
m=strlen(s2);
for(i=1; i<n; i++)
{
while(k>0 && s1[i]!=s1[k])
k=pi[k-1];
if(s1[i]==s1[k])
k++;
pi[i]=k;
}
k=0;
for(i=0; i<m; i++)
{
while(k>0 && s2[i]!=s1[k])
k=pi[k-1];
if(s2[i]==s1[k])
k++;
if(k==n)
{
k=pi[n-1];
sol[++j]=i-n+1;
}
}
g<<j<<'\n';
j=(j<1000)?j:1000;
g<<sol[1];
for(i=2; i<=j; i++)
g<<" "<<sol[i];
f.close(); g.close();
return 0;
}