Pagini recente » Cod sursa (job #3250178) | Cod sursa (job #2551356) | Cod sursa (job #934727) | Cod sursa (job #2456313) | Cod sursa (job #1210230)
#include<iostream>
#include<fstream>
#include <string.h>
#include <algorithm>
using namespace std;
int M, N;
char sir1[2000000], sir2[2000000];
int pi[2000000], p[1024];
ifstream f("strmatch.in");
ofstream g("strmatch.out");
void pref(){
int i;
int q = 0;
pi[1] = 0;
for(i = 2; i <= M; i++)
{while(q && sir1[q + 1] != sir1[i])
q = pi[q];
if (sir1[q + 1] == sir2[i])
q++;
pi[i] = q;
}
}
int main(){
f.get(sir1,2000000);
f.get();
f.get(sir2,2000000);
f.get();
M = strlen(sir1 + 1);
N = strlen(sir2 + 1);
pref();
int q = 0, nr = 0;
for(int i = 1; i <= N; i++){
while (q && sir1[q + 1] != sir2[i])
q = pi[q];
if (sir1[q + 1] ==sir2[i])
++q;
if (q == M){
nr++;
if ( nr <= 1000)
p[nr] = i - q;
}
}
g<<nr<<endl;
for (int i = 1; i<=nr; i++)
g<<p[i]<<" ";
f.close();
f.close();
}