Pagini recente » Cod sursa (job #2090694) | Cod sursa (job #232999) | Cod sursa (job #544586) | Cod sursa (job #1895505) | Cod sursa (job #810703)
Cod sursa(job #810703)
#include <fstream>
#include <cstring>
#define NMAX 2000004
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char sir[NMAX],strg[NMAX];
int N,M;
int Next[NMAX],Rez[1002];
void Prefix()
{
int k=0,i;
for(i = 2, Next[1] = 0; i<=N;i++)
{
while(k&&sir[k+1]!=sir[i])
k = Next[k];
if(sir[k+1] == sir [i])
k++;
Next[i] = k;
}
}
int main()
{
int i,k = 0,nr = 0;
in>>sir>>strg;
N = strlen(sir);
M = strlen(strg);
for(i=N;i;i--)
sir[i] = sir[i-1];
sir[0] = ' ';
Prefix();
for(i=M;i;i--)
strg[i] = strg[i-1];
strg[0] = ' ';
for(i=1;i<=M;i++)
{
while(k&&sir[k+1]!=strg[i])
k = Next[k];
if(sir[k+1] == strg[i])
k++;
if(k == N)
{
k = Next[k];
nr ++;
if(nr<=1000)
Rez[nr] = i - N;
}
}
out<<nr<<'\n';
for(i=1;i<=nr&&i<=1000;i++)
out<<Rez[i]<<' ';
return 0;
}