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