Pagini recente » Cod sursa (job #1661289) | Cod sursa (job #507941) | Monitorul de evaluare | Rating Gabriel Costea (gcostea) | Cod sursa (job #880618)
Cod sursa(job #880618)
#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 1005
#define ll long long
#define Sirmax 2000005
string A, B;
int rez[Sirmax], pi[Sirmax];
void citeste(){
getline(f,A);
getline(f,B);
// le reindexez de la 1
A += '#'; B += '#';
for(int i=A.size()-1; i>=1; --i) A[i] = A[i-1];
for(int i=B.size()-1; i>=1; --i) B[i] = B[i-1];
}
void prefix(){
for(int i=2, q=0; i<A.size(); ++i){
while( q>0 && A[q+1] != A[i]) q = pi[q];// ideea ar fi ca acum tot tai din prefixe
// cand ma opresc insemana ca cel mai lung prefix care e sufix are lungimea q
// incerc sa il fac de lungime q+1;
if (A[q+1] == A[i]) ++q;
pi[i] = q;
}
}
void rezolva(){
// imi fac functia prefix care o sa imi zice pentru sirul pi[i] = cel mai lung prefix 1...i care e sufix a acestei secvente
prefix();
//acum vad aparitiile
int sz=0;
for(int i=1,q=0; i<B.size(); ++i){
while(q>0 && A[q+1] != B[i]) q = pi[q];// tot incerc urmatoarele potriviri
if (A[q+1] == B[i]) q++;
if (q == A.size() - 1){
q = pi[q];
rez[++sz] = i- (A.size()-1);// is indexate de la 0 (cere in enut)
}
}
g << sz << "\n";
//cout << sz << "\n";
for(int i=1; i<=min(sz, 1000); ++i){
//cout << rez[i]<< "\n";
g << rez[i]<< " ";
}
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}