Pagini recente » Cod sursa (job #7925) | Cod sursa (job #2894499) | Cod sursa (job #693080) | Cod sursa (job #2296860) | Cod sursa (job #2684827)
#include <iostream>
#include <fstream>
#include <cstring>
#define NMAX 2000002
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char a[NMAX], b[NMAX];
int p[NMAX], afis[NMAX];
int main()
{
int n, m, i, j, nr_afis=0;
fin.getline(a, NMAX); n=strlen(a);
fin.getline(b, NMAX); m=strlen(b);
j=0; p[1]=0;
for(i=1; i<n; i++)
{
while(j!=0&&a[i]!=a[j])j=p[j-1];
if(a[i]==a[j]) j++;
p[i]=j;
}
//for(i=0; i<n; i++) cout<<p[i<<' ';
j=0;
for(i=0; i<m && nr_afis<1000; i++)
{
while(j!=0&&a[j]!=b[i])
{
j=p[j-1];
}
if(a[j]==b[i]) j++;
if(j==n) //am gasit o pozitie
{
afis[++nr_afis]=i-n+1;
}
}
fout<<nr_afis<<"\n";
for(i=1; i<=nr_afis; i++) fout<<afis[i]<<' ';
}