Pagini recente » Cod sursa (job #514667) | Cod sursa (job #2406881) | Cod sursa (job #995562) | Cod sursa (job #618034) | Cod sursa (job #2119573)
#include <iostream>
#include <bits/stdc++.h>
#define INFILE "strmatch.in"
#define OUTFILE "strmatch.out"
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
vector<int> ComputeZVector(string str){
vector<int> Z(str.size(),0);
int L=0;
int R=0;
for(int k=1;k<str.size();k++){
if(R<k){
R=L=k;
while(R<str.size()&&str[R]==str[R-L])
R++;
Z[k]=R-L;
R--;
}
else{
int k1=k-L;
if(Z[k1]<R-k+1){
Z[k]=Z[k1];
}
else{
L=k;
while(R<str.size()&&str[R]==str[R-L])
R++;
Z[k]=R-L;
R--;
}
}
}
return Z;
}
vector<int> ZAlgoritm(string haysack,string needle){
string prepreocess=needle+"$"+haysack;
vector<int> Z=ComputeZVector(prepreocess);
vector<int> ret;
for(int i=needle.size();i<Z.size();i++){
if(Z[i]==needle.size())
ret.push_back(i-needle.size()-1);
}
return ret;
}
int main()
{
string needle,haysack;
vector<int> ret;
in>>needle>>haysack;
ret=ZAlgoritm(haysack,needle);
out<<ret.size()<<"\n";
for(auto x:ret)
out<<x<<" ";
return 0;
}