Pagini recente » Cod sursa (job #1847851) | Cod sursa (job #1955944) | Cod sursa (job #779831) | Cod sursa (job #494567) | Cod sursa (job #984851)
Cod sursa(job #984851)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
char s1[2000007],s[2000007];
int urm[2000007],n1,q,i,n,k,rasp[2000007];
int f1(int q)
{
while (q>1)
{
q=urm[q-1];
if (s1[i]==s1[q])
return q+1;
}
return q;
}
int main(void)
{
FILE * f;
f=fopen("strmatch.in","r");
ofstream g("strmatch.out");
fgets(s1,2000005,f);
fgets(s,2000005,f);
n1=strlen(s1)-1;
q=0;
for (i=1;i<n1;i++)
{
if (s1[i]==s1[q])
q++;
else
q=f1(q);
if (q<=1)
{
if (s1[i]==s1[0])
q=1;
else
q=0;
}
urm[i]=q;
}
n=strlen(s)-1;
q=0;
for (i=0;i<n;i++)
{
while ((s[i]!=s1[q])&&(q>0))
q=urm[q-1];
if (q==0)
while (s[i]!=s1[0])
i++;
q++;
if (q==n1)
{
k++;
rasp[k]=i-n1+1;
}
}
g<<k<<'\n';
for (i=1;i<=k;i++)
g<<rasp[i]<<' ';
g.close();
return 0;
}