Pagini recente » Cod sursa (job #2838568) | Cod sursa (job #2148969) | Cod sursa (job #409259) | Cod sursa (job #2901247) | Cod sursa (job #2586467)
//Rabin Karp
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const long long MOD = (1LL << 30);
const long long PRIME = 101;
string a,b;
long long hashA,hashB,PUTERE;
vector<int>sol;
bool match(int start){
for(int i = 0;i < a.size();++i)
if(a[i] != b[i + start])
return false;
return true;
}
int main(){
f >> a >> b;
int n = (int)a.size();
int m = (int)b.size();
if(n > m){
g << 0;
return 0;
}
PUTERE = 1;
for(int i = 0;i < n;++i){
hashA += a[i] * PUTERE;
hashB += b[i] * PUTERE;
PUTERE = (PUTERE * PRIME) % MOD;
}
if(hashA == hashB && match(0))
sol.push_back(0);
for(int i = n;i < m;++i){
hashB = hashB - b[i - n];
hashB /= PRIME;
hashB = (hashB + b[i] * PUTERE) % MOD;
if(hashB < 0)
hashB += MOD;
if(hashA == hashB && match(i - n + 1))
sol.push_back(i - n + 1);
}
g << sol.size() << '\n';
for(int i = 0;i < sol.size() && i < 1000;++i)
g << sol[i] << ' ';
return 0;
}