Pagini recente » Cod sursa (job #1255022) | Monitorul de evaluare | Rating Vacaru Raluca-Ioana (raluca_vacaru) | Rating Arhip Georgiana (arhip_georgiana_323ca) | Cod sursa (job #1093011)
#include <iostream>
#include <string.h>
#include <cstdio>
#include <fstream>
#define Nmax 2000000
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char T[Nmax],P[Nmax];
int Urm[Nmax],m,n,v[1001];
bool ok=false;
void citire()
{
f.getline(P,Nmax);
f.getline(T,Nmax);
f.close();
}
void urmatorul(char *P)
{
int k=-1,x;
Urm[0]=0;
for(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()
{
citire();
n=strlen(T);
m=strlen(P);
int i,x=-1,j=0;
urmatorul(P);
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)
{
if (j<1000)
{
++j;
v[j]=i-m+1;
}
x=Urm[x];
}
}
g<<j<<"\n";
for(i=1;i<=j;++i) g<<v[i]<<" ";
g.close();
return 0;
}