Pagini recente » Cod sursa (job #1718258) | Cod sursa (job #2320139) | Cod sursa (job #1928947) | Cod sursa (job #647799) | Cod sursa (job #908159)
Cod sursa(job #908159)
#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 ll long long
#define nmax 2000005
string S, P, T;
int z[nmax*2];
int rez[1004];
void citeste(){
getline(f, P);
getline(f, T);
S = P + T;
S += '#'; for(int i=S.size()-1; i>=1; --i) S[i] = S[i-1];// l-am indexat de la 1
/*
for(int i=1; i<=14; ++i) cout << S[i];
cout << "\n";
*/
}
int compara(int x, int y){
int cnt = 0;
for(int i=x, j=y; i<S.size(); ++i, ++j){
if (S[i] != S[j]) return cnt;
++cnt;
}
return cnt;
}
void Zvalues(){
z[1] = S.size()-1;// dimensiunea stringului original e S.size()-1 pt ca am adaug caracaterul '#';
int st = 1; int dr = 1;
for(int i=2; i<S.size(); ++i){
//cout << st << " " << dr << " " << i-1 << "\n";
if (dr < i){
z[i] = compara(i, 1);// cat de mult ma pot duce in dreapta
if (z[i] != 0) {
st = i;
dr = i + z[i] - 1;
}
//cout << st << " " << dr << " " << i << "\n";
continue;
}else {// dr >= i
int Lung = dr - i + 1;
int dr2 = 1 + (dr-st+1) - 1;
int i1 = dr2 - Lung + 1;
if (z[i1] < Lung){// se vede de ce pe foaie
//cout << i << " " << i1 << "\n";
z[i] = z[i1];
//cout << st << " " << dr << " " << i << "\n";
continue;
}
if (z[i1] > Lung){// se vede de ce pe foaie
z[i] = Lung;
// cout << st << " " << dr << " " << i << "\n";
continue;
}
z[i] = z[i1] + compara(dr+1, Lung+1);
//if (z[i] != z[i1])
st = i, dr = i + z[i] - 1;
//cout << st << " " << dr << " " << i-1 << "\n";
}
}
/*
for(int i=P.size()+1; i<S.size(); ++i){
cout << z[i] << " ";
}
cout << "\n";
*/
}
void rezolva(){
// il fac cu Zalgorithm; in primul rand zalgorithm care ca si idee zvalues; acestea se fac pe un string S;
// fie z[i] = cea mai lunga secvente ce incepe in i si e la fel cu prefixul de lungime;
// adica z[i] = x; => ca secventa [i...i+x-1] e la fel cu secventa [1..1+x-1];
// si pentru a gasi aparatiile fac in felul urmator la pattern mai adaug textul si bag zalgorithm
// la sfarsit pentru fiecare i > pattern.size() cu z[i] >= parttern.size() am gasit o apartie a patternului in text
// acum zvalues le fac in felul urmator; cazul particular z[1] = S.size();
// asa ca incep de la pozitia 2; pe parcursul iteratiilor tin 2 indici st si dr; care imi indica cea mai din dreapta
// secventa gasita pana la pasul curent care apare in prefix( fie ea zBox);
// bun z[i] il aflu pe baza lui i-1; mai exact o sa am 2 cazuri iar in al 2 lea caz o sa am 3
// primul caz; dr < i => o sa compar de la pozitia i pana cand gasesc o nepotrivire;
// al 2 lea caz; dr >= i; aici am asa ; definesc dr2 = 1 + (dr-st+1) - 1 si i2 ca fiind 1 + ( dr - k + 1 ) - 1 si
//fie A = secventa [i..dr]; ea evident == cu [i1..dr2];
// 2.a) z[i2] < A.size() ( == dr2 - i2 + 1) => z[i] = z[i2]; e evident pentru ca inseamna ca cea lunga secventa e < ca si A.size() deci de la A.size()+1 nu concind caracter;
// 2.b) z[i2] > A.size() => z[i] = A.size(); e egal cu A.size() pt ca; hai sa pp ca nu e la fel asta inseamna ca S[dr+1] == cu S[dr2+1] deci secventa st...dr (cand am facuto) putea fi marita si nu a fost
// => z[i] = A.size();
// 2.c) z[i2] == A.size() => aici o sa caut o nepotrivire de la dr+1 incolo pt ca nu pot deduce nici cum ce urmeaza
Zvalues();
int p = P.size(); int sz = 0;
//cout << p << "\n";
for(int i=p+1; i<S.size(); ++i){
if (z[i] >= p){// >= pt ca s-ar putea ca secventa de incepe pe i sa fie mai mare ca si p
if (sz < 1000){
rez[++sz] = i-p-1;// problema din arhiva le are indexate de la 0
}else ++sz;
}
}
g << sz << "\n";
sz = min(sz, 1000);
for(int i=1; i<=sz; ++i){
g << rez[i] << " ";
}
g << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}