Pagini recente » Cod sursa (job #910003) | Cod sursa (job #1921144) | Cod sursa (job #2282521) | Cod sursa (job #2317761) | Cod sursa (job #2277169)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int P[2000055],i,q,nrsol,sol[2000055];
char v[2000055],t[2000055];
void kmp(int n){
P[1]=0;
for(i=2;i<=n;i++){
q=P[i-1];
while(q&&v[i]!=v[q+1])
q = P[q];
if(v[i]==v[q+1])
q++;
P[i]=q;
}
}
int main()
{
f>>v+1;
f>>t+1;
int n= strlen(t+1);
int len=strlen(v+1);
int q=0;
kmp(len);
for(i=1;i<=n;i++){
while( q && t[i] != v[q+1])
q=P[q];
if(t[i]==v[q+1])
q++;
if(q == len){
q = P[len];
nrsol ++;
sol[nrsol]=i-len;
}
}
g<<nrsol<<'\n';
for(i=1;i<=min(nrsol,1000);i++)
g<<sol[i]<<" ";
return 0;
}