Pagini recente » Cod sursa (job #896950) | Cod sursa (job #947607) | Cod sursa (job #2126594) | Cod sursa (job #1759402) | Cod sursa (job #1210236)
#include<iostream>
#include<fstream>
#include <string.h>
#include <algorithm>
using namespace std;
int M, N;
char sir1[2000001], sir2[2000001];
int pi[2000001], 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,2000001);
f.get();
f.get(sir2,2000001);
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 <= std::min(nr, 1000); i++)
g<<p[i]<<" ";
f.close();
f.close();
}