Pagini recente » Cod sursa (job #1797668) | Cod sursa (job #2129695) | Cod sursa (job #650447) | Cod sursa (job #2360739) | Cod sursa (job #2515759)
#include <stdio.h>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
//FILE *fin = fopen("strmatch.in", "r");
//FILE *fout = fopen("strmatch.out", "w");
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int DIM = 2e6 + 7;
int p,t,i,j,lps[2000005],nrap,ap[1001],k,lg;
char patt[2000005],txt[2000005];
int main()
{
//fgets(patt+1, 2000005, fin);
// fgets(txt+1, 2000005, fin);
fin.getline( patt + 1, DIM - 5 );
fin.getline( txt + 1, DIM - 5 );
p = strlen( patt + 1 );
t = strlen( txt + 1 );
patt[0] = txt[0] = '.';
// p = strlen(patt) - 2;
// t = strlen(txt) - 2;
lps[0] = -1;lps[1]=0;
lg=0;
//lg indica cate caractere aflate la inceputul cuvantului sunt identice cu caracterele aflate pana la i-1(inclusiv)
for(i=2; i<=p; ++i){
while(lg>0 and patt[i]!=patt[lg+1])
lg=lps[lg];
if(patt[i]==patt[lg+1])
lg++;
lps[i]=lg;
}
i = 1; j = 1;lg=0;
//lg reprezinta cate caractere de la inceputul lui patt sunt egale cu cele aflate in txt, pana la i-1(inclusiv)
while(i<=t and nrap<1000)
{
while(lg>0 and txt[i]!=patt[lg+1])
lg=lps[lg];
if(txt[i]==patt[lg+1])
lg++;
if(lg==p)
{
ap[++nrap]=i-p;
lg=lps[p];
}
i++;
}
// fprintf(fout, "%d\n", nrap);
fout<<nrap<<'\n';
for(i=1; i<=nrap; ++i)
fout<<ap[i]<<' ';
//fclose(fin);
// fclose(fout);
return 0;
}