Pagini recente » Cod sursa (job #580872) | Cod sursa (job #1510219) | Cod sursa (job #734746) | Cod sursa (job #2244533) | Cod sursa (job #932260)
Cod sursa(job #932260)
#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, S;
int z[nmax*2], rez[nmax];
void citeste(){
getline(f, P);
getline(f, T);
}
inline int compara(int x, int y){
int cnt = 0;
for(int i=x, j=y; j<S.size(); ++i, ++j){
if(S[i] != S[j]) return cnt;
++cnt;
}
return cnt;
}
void bagaZvalues(){
// z[i] = cea mai lunga secventa ce incepe pe pozitia i si e prefix la secventa initiala
S = P + T;
z[0] = S.size();
int st = -1; int dr = -1;
for(int i=1; i<S.size(); ++i){
if (i > dr){// e in afara zBox-ului
z[i] = compara(0, i);
if (z[i] != 0){
st = i; dr = i + z[i]- 1;
}
continue;
}else {
int lungAlpha = dr - st + 1; int lungBeta = dr - i + 1;
int dr2 = 0 + lungAlpha - 1; int i2 = dr2 - lungBeta + 1;
if (z[i2] < lungBeta){
z[i] = z[i2]; continue;
}
if (z[i2] > lungBeta){
z[i] = lungBeta; continue;
}
z[i] = lungBeta + compara(lungBeta, dr+1);
if (i + z[i]-1 > dr){
st = i; dr = i + z[i] - 1;
}
}
}
}
void rezolva(){
bagaZvalues();
for(int i=P.size(); i<S.size(); ++i){
//cout << z[i] << " ";
if (z[i] >= P.size()){
rez[++rez[0]] = i - P.size();
}
}
g << rez[0] << "\n";
//cout << rez[0] << "\n";
rez[0] = min(rez[0], 1000);
for(int i=1; i<=rez[0]; ++i){
//cout << rez[i] << " ";
g << rez[i] << " ";
}
g << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}