Pagini recente » Cod sursa (job #2653175) | Cod sursa (job #3171053) | Cod sursa (job #1389408) | Cod sursa (job #2661184) | Cod sursa (job #761916)
Cod sursa(job #761916)
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char p[2000010],t[2000010];
long fct[2000005],lgp,lgt,x,v[1005];
int main()
{
long i;
f.getline(p,2000005,'\n');
f.getline(t,2000005,'\n');
lgp=strlen(p);
lgt=strlen(t);
fct[0]=-1;
for(i=1;i<lgp;i++){
x=fct[i-1];
while(x>=0&&p[x+1]!=p[i])
x=fct[x];
if(p[x+1]==p[i])
x++;
fct[i]=x;}
x=-1;
for(i=0;i<lgt;i++){
while(x>=0&&t[i]!=p[x+1])
x=fct[x];
if(t[i]==p[x+1])
x++;
if(x==lgp-1){
v[0]++;
v[v[0]]=i-lgp+1;
if(v[0]==1000)
break;}}
g<<v[0]<<'\n';
for(i=1;i<=v[0];i++)
g<<v[i]<<' ';
f.close();
g.close();
return 0;
}