Pagini recente » Cod sursa (job #850006) | Cod sursa (job #2007739) | Cod sursa (job #563714) | Cod sursa (job #572085) | Cod sursa (job #1200091)
#include<iostream>
#include<fstream>
#include<string>
#define NMAX 2000005
#define MMAX 2000005
#define minim(a,b) ((a<b)?a:b)
using namespace std;
int N, M,pi[NMAX],pos[1024];
string P, S;
void f_prefix(){
pi[1] = 0;
int q = 0;
for (int i = 2; i < M; ++i){
while (q && P[q + 1] != P[i]){
q = pi[q];
}
if (P[q + 1] == P[i])
q++;
pi[i] = q;
}
}
int main(){
ifstream f("strmatch.in", ios::in);//Change the name
ofstream g("strmatch.out", ios::out);//Change the name
f >> P;
f >> S;
P.push_back(' ');
for (int i = P.size()-1; i; --i)
P[i] = P[i - 1];
S.push_back(' ');
for (int i = S.size() - 1; i; --i)
S[i] = S[i - 1];
M = P.size();
N = S.size();
f_prefix();
int q = 0,n = 0;
for (int i = 1; i < N; ++i){
while (q && P[q + 1] != S[i])
q = pi[q];
if (P[q + 1] == S[i])
q++;
if (q == M - 1){
q = pi[M-1];
++n;
if (n<=1000)
pos[n] = i - M +1;
}
}
g << n << '\n';
for (int i = 1; i <=minim(n,1000); ++i)
g << pos[i] << ' ';
g << '\n';
f.close();
g.close();
return 0;
}