Pagini recente » Cod sursa (job #439664) | Cod sursa (job #1584150) | Rating Iulian Mone (iulian_mone) | agm | Cod sursa (job #899996)
Cod sursa(job #899996)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define nmax 2000005
#define ll long long
string P, T;
int pi[nmax], Pn, Tn, rez[1005];
void citeste(){
getline(f, P);
getline(f, T);
// le reindexez;
P += '#'; T += '#';
for(int i=P.size()-1; i>=1; --i) P[i] = P[i-1];
for(int i=T.size()-1; i>=1; --i) T[i] = T[i-1];
Pn = P.size()-1; Tn = T.size()-1;
}
void prefix(){
pi[1] = 0;
for(int i=2, q=0; i<=Pn; ++i){
while(q>0 && P[q+1] != P[i]) q=pi[q];
if (P[q+1] == P[i]) ++q;
pi[i] = q;
}
}
void bagaKmp(){
for(int i=1, q=0; i<=Tn; ++i){
while( q>0 && P[q+1] != T[i]) q= pi[q];
if (P[q+1] == T[i]) ++q;
if (q == Pn){// am gasit o aparitie
++rez[0];
if (rez[0] <= 1000) rez[rez[0]] = i-Pn;
}
}
}
void rezolva(){
prefix();
bagaKmp();
g << rez[0] << "\n";
rez[0] = min(rez[0], 1000);
for(int i=1; i<=rez[0]; ++i) g << rez[i] << " ";
g << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}