Pagini recente » Cod sursa (job #2849691) | Cod sursa (job #3126288) | Cod sursa (job #1834032) | Cod sursa (job #2422898) | Cod sursa (job #2586466)
//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;
long long lgput(long long a,long long b){
long long r = 1;
while(b){
if(b & 1)
r = r * a;
a = (a * a) % MOD;
b >>= 1;
}
return r;
}
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;
}
for(int i = 0;i < n;++i){
PUTERE = lgput(PRIME,i);
hashA += a[i] * PUTERE;
hashB += b[i] * PUTERE;
}
if(hashA == hashB && match(0))
sol.push_back(0);
for(int i = n;i < m;++i){
hashB = hashB - b[i - n];
hashB /= PRIME;
hashB += b[i] * PUTERE;
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;
}