Pagini recente » Cod sursa (job #404272) | Cod sursa (job #2665711) | Cod sursa (job #515142) | Cod sursa (job #2196981) | Cod sursa (job #1558436)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char t[2000001],p[2000001];
int pi[2000001],n,m,nr,ap[2000001],testate,start;
int i,k,j;
int main()
{
f>>p>>t;
k = 0; pi[0] = 0;
n = strlen(t); m= strlen(p);
//g<<p<<"\n"<<t;
for(i = 1; i < m; i++){
while(k>0 && p[i] != p[k]) k = pi[k-1];
if(p[i] == p[k]) k = k + 1;
pi[i] = k;
}
start = 0; testate = 0;
while (i < n){
j = testate;
i = start + testate;
k = testate;
while(i<n && j<m && t[i] == p[j]) {
i++;j++;k++;
}
if(k == m) {
ap[nr] = start;
nr = nr + 1;
}
if(k == 0) { start = start + 1; testate = 0; }
else {start = start + k - pi[k-1]; testate = pi[k-1];}
}
g<<nr<<"\n";
if(nr>1000) nr = 1000;
for(i = 0; i < nr; i++) g<<ap[i]<<" ";
return 0;
}