Pagini recente » Cod sursa (job #2211810) | Cod sursa (job #467740) | Cod sursa (job #2708981) | Cod sursa (job #1129276) | Cod sursa (job #2409696)
#include <fstream>
#include <string>
#include <vector>
#define MOD1 666013
#define MOD2 666019
using namespace std;
ifstream in ("strmatch.in");
ofstream out("strmatch.out");
string str1, str2;
int hashSmall1, hashSmall2, hashBig1, hashBig2, pow1 = 1, pow2 = 1;
int BASE = 59, nrSol;
vector<int> sol;
int main(int argc, const char * argv[]) {
in>>str1>>str2;
if(str1.size() > str2.size()){
out<<0;
return 0;
}
//ABC
for(auto it : str1){
hashSmall1 = (hashSmall1 * BASE + it - 'A') % MOD1;
hashSmall2 = (hashSmall2 * BASE + it - 'A') % MOD2;
}
for(int i = 0; i < str1.size(); ++ i){
hashBig1 = (hashBig1 * BASE + str2[i] - 'A') % MOD1;
hashBig2 = (hashBig2 * BASE + str2[i] - 'A') % MOD2;
if(i != 0){
pow1 = (pow1 * BASE) % MOD1;
pow2 = (pow2 * BASE) % MOD2;
}
}
if(hashBig1 == hashSmall1 && hashBig2 == hashSmall2){
++ nrSol;
sol.push_back(0);
}
for(int i = str1.size(); i < str2.size(); ++ i){
hashBig1 = hashBig1 - pow1 * (str2[i - str1.size()] - 'A') % MOD1;
while(hashBig1 < 0)
hashBig1 += MOD1;
hashBig2 = hashBig2 - pow2 * (str2[i - str1.size()] - 'A') % MOD2;
while(hashBig2 < 0)
hashBig2 += MOD2;
hashBig1 = (hashBig1 * BASE + str2[i] - 'A') % MOD1;
hashBig2 = (hashBig2 * BASE + str2[i] - 'A') % MOD2;
if(hashBig1 == hashSmall1 && hashBig2 == hashSmall2){
++ nrSol;
if(nrSol < 1000)
sol.push_back(i - str1.size() + 1);
}
}
out<<nrSol<<'\n';
for(auto it : sol)
out<<it<<" ";
return 0;
}