Pagini recente » Cod sursa (job #1117299) | Cod sursa (job #1730120) | Cod sursa (job #2259516) | Cod sursa (job #1941011) | Cod sursa (job #2675182)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
typedef string::const_iterator sit;
class Roller{
private:
int a, n;
int ap = 1;
int q = 0;
public:
Roller();
Roller(int a, int n, sit lt, sit rt) : a(a), n(n){
for(auto it = lt; it != rt; ++it){
q *= a;
q += *it;
q %= n;
if(it!=lt)ap *= a;
ap %= n;
}
}
Roller(int a, int n, const string &str) : Roller(a,n,str.begin(),str.end()){}
Roller(int a, int n, const string &str, int len) : Roller(a,n,str.begin(),str.begin()+len){}
void roll(char out, char in){
q -= out*ap;
q += n*128;
q %= n;
q *= a;
q += in;
q %= n;
}
bool operator==(const Roller &rhs){
return q == rhs.q;
}
};
const int a = 31;
const int n1 = 1000003, n2 = 1000033;
string pattern, text;
int ans1 = 0;
vector<int> ans2;
int main(){
// ios_base::sync_with_stdio(false);
fin >> pattern >> text;
Roller rpattern[] = {Roller(a,n1,pattern),Roller(a,n2,pattern)};
Roller rtext[] = {Roller(a,n1,text,pattern.size()),Roller(a,n2,text,pattern.size())};
if(rpattern[0] == rtext[0] && rpattern[1] == rtext[1]){
ans1++;
if(ans1 <= 1000)ans2.push_back(0);
}
for(int i = pattern.size(); i < text.size(); ++i){
rtext[0].roll(text[i-pattern.size()], text[i]);
rtext[1].roll(text[i-pattern.size()], text[i]);
if(rpattern[0] == rtext[0] && rpattern[1] == rtext[1]){
ans1++;
if(ans1 <= 1000)ans2.push_back(i-pattern.size()+1);
}
}
fout << ans1 << "\n";
for(auto a : ans2)fout << a << " ";
return 0;
}