Pagini recente » Cod sursa (job #3217940) | Cod sursa (job #2944786) | Cod sursa (job #2205937) | Cod sursa (job #1635164) | Cod sursa (job #1504919)
#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,k,nr,n,m;
void prefix (int n)
{
pref[0]=0;
i=0;
for (j=1;j<n;j++)
{
while (i>0 && p[i]!=p[j])
i=pref[i];
if (p[i]==p[j])
i++;
pref[j]=i;
}
}
void rezultat (int n, int m)
{
i=0;
j=0;
k=0;
while (n-k>=m-1)
{
while (j<=m-1 && s[i]==p[j])
{
i++;
j++;
}
if (j>m-1)
{
nr++;
rez[nr]=k;
}
if (pref[j-1]>0)
k=i-pref[j-1];
else
{
if (i==k)
i++;
k=i;
}
if (j>0)
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;
}