Pagini recente » Cod sursa (job #2568117) | Cod sursa (job #2648604) | Cod sursa (job #2857461) | Cod sursa (job #2137354) | Cod sursa (job #3280741)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char s1[2000005],s2[2000005],s[4000005];
int n,m,st,dr,k,sol[1001],z[4000005];
int main()
{
fin>>s1>>s2;
strcat (s+1,s1);
m=strlen (s+1);
strcat (s+1,"*");
strcat (s+1,s2);
n=strlen (s+1);
z[1]=n;
for (int i=1; i<=n; i++)
{
if (i<=dr)
z[i]=min (z[i-st+1],dr-i+1);
while (i+z[i]<=n&&s[i+z[i]]==s[z[i]+1])
z[i]++;
if (i>m+1&&z[i]==m)
{
k++;
if (k<=1000)
sol[k]=i-(m+2);
}
if (i+z[i]-1>dr)
{
dr=i+z[i]-1;
st=i;
}
}
fout<<k<<"\n";
for (int i=1; i<=k; i++)
fout<<sol[i]<<" ";
return 0;
}