Pagini recente » Cod sursa (job #620922) | Cod sursa (job #227498) | Cod sursa (job #613286) | Cod sursa (job #394168) | Cod sursa (job #3241167)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int i,nr,n,m,urm[20000010],a[1009];
char T[2000010],P[2000010];
void urmatorul(char *P)
{
int k=-1;
urm[0]=0;
for(int x=1; x<m; x++)
{
while(k>=0 && P[k+1]!=P[x])
{
k=urm[k];
}
if(P[k+1]==P[x])
{
k++;
}
urm[x]=k;
}
}
int main()
{
int x=-1;
fin.getline(P,2000009);
fin.getline(T,2000009);
n=strlen(T);
m=strlen(P);
if(m>n)
{
fout<< 0;
return 0;
}
urmatorul(P);
nr=0;
for(i=0; i<n; i++)
{
while(x>0 && P[x+1]!=T[i])
{
x=urm[x];
}
if(P[x+1]==T[i])
{
x++;
}
if(x==m-1)
{
nr++;
if(nr<=1000)
{
a[nr]=i;
}
x=urm[x];
}
}
fout<< nr << "\n";
for(i=1; i<=min(nr,1000); i++)
{
fout<< a[i]-m+1 << " ";
}
return 0;
}