Pagini recente » Cod sursa (job #2373294) | Cod sursa (job #703272) | Cod sursa (job #569609) | Cod sursa (job #2878221) | Cod sursa (job #1509032)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char p[2000010],s[2000010];
int pref[2000010],rez[1010];
int i,j,nr,n,m;
void prefix (int n)
{
pref[0]=0;
i=1;
j=0;
while (i<n)
{
if (p[i]==p[j])
{
pref[i]=j+1;
i++;
j++;
}
else
if (j==0)
pref[i++]=0;
else
j=pref[j-1];
}
}
void rezultat (int n, int m)
{
i=0;
j=0;
while (i<n)
{
if (s[i]==p[j])
{
i++;
j++;
if (j==m)
{
nr++;
rez[nr]=i-m;
j=pref[j-1];
}
}
else
if (j==0)
i++;
else
j=pref[j-1];
}
}
int main()
{
fin.getline (p,2000010);
fin.getline (s,2000010);
n=strlen(p);
prefix(n);
n=strlen(s);
m=strlen(p);
rezultat(n,m);
fout<<nr<<"\n";
i=1;
while (i<=nr && i<=1000)
{
fout<<rez[i]<<" ";
i++;
}
return 0;
}