Pagini recente » Clasament pregatireoni-cls5 | Cod sursa (job #1066856) | Cod sursa (job #2291490) | Cod sursa (job #1306931) | Cod sursa (job #1199600)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
class ZAlgorithm{
public:
ZAlgorithm(){}
ZAlgorithm(const string& text){
//cout << text << "\n";
this->S = text;
this->makeZValues();
}
vector<int>& getZValues(){
return this->zValues;
}
private:
vector<int> zValues;
string S;
int compara(const int &x,const int &y){
int cnt = 0;
for(int i=x, j=y; j<(int)S.size(); ++i, ++j){
if(S[i] != S[j]) return cnt;
++cnt;
}
return cnt;
}
void makeZValues(){
zValues.assign((int)S.size(), 0);
zValues[0] = S.size();
int L = -1; int R = -1;
for(int i=1; i<S.size(); ++i){
if (i > R){
zValues[i] = compara(0, i);
if (zValues[i] != 0){
L = i; R = i + zValues[i]- 1;
}
}else {
int lungA = R - L + 1; int lungB = R - i + 1;
int R2 = 0 + lungA - 1; int i2 = R2 - lungB + 1;
if (zValues[i2] < lungB){
zValues[i] = zValues[i2]; continue;
}
zValues[i] = lungB + compara(lungB, R+1);
if (i + zValues[i]-1 > R){
L = i; R = i + zValues[i] - 1;
}
}
}
}
};
int main(){
ifstream f("strmatch.in");
string text, pattern;
getline(f, pattern);
getline(f, text);
string S = pattern + text;
ZAlgorithm *X = new ZAlgorithm(S);
vector<int> z = X->getZValues();
vector<int> ans;
int cnt = 0;
for(int i=(int)pattern.size(); i<S.size(); ++i){
if (z[i] >= pattern.size()){
++cnt;
if(ans.size() < 1000) ans.push_back(i-(int)pattern.size());
}
}
f.close();
ofstream g("strmatch.out");
g << cnt << "\n";
for(int i=0; i<(int)ans.size(); ++i){
g << ans[i] << " ";
}
g.close();
}