Pagini recente » Cod sursa (job #868107) | Cod sursa (job #440377) | Cod sursa (job #1638710) | Cod sursa (job #249283) | Cod sursa (job #2515777)
#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[DIM],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 )-1;
t = strlen( txt + 1 )-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 )
{
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';
if(nrap>1000) nrap=1000;
for(i=1; i<=nrap; ++i)
fprintf(fout,"%d ",ap[i]);
// fout<<ap[i]<<' ';
fclose(fin);
fclose(fout);
return 0;
}