Pagini recente » Cod sursa (job #2436454) | Cod sursa (job #523672) | Cod sursa (job #2320839) | Cod sursa (job #2547175) | Cod sursa (job #1558434)
#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];
int i,k;
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;
}
k = 0;
for(i = 0; i < n; i++){
while(k>0 && t[i]!=p[k]) k = pi[k-1];
if(t[i] == p[k]) k = k + 1;
if(k == m){
ap[nr] = i - m + 1;
nr = nr + 1;
k = pi[k-1];
}
}
g<<nr<<"\n";
if(nr>1000) nr = 1000;
for(i = 0; i < nr; i++) g<<ap[i]<<" ";
return 0;
}