Pagini recente » Cod sursa (job #1565651) | Cod sursa (job #2796285) | Cod sursa (job #1598083) | Cod sursa (job #1039314) | Cod sursa (job #2586471)
//Rabin Karp
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
typedef long long ll;
const long long MOD = (1LL << 30);
const long long PRIME = 31;
string a,b;
long long hashA,hashB,PUTERE;
vector<long long>sol;
bool match(long long start){
for(ll i = 0;i < a.size();++i)
if(a[i] != b[i + start])
return false;
return true;
}
int main(){
f >> a >> b;
ll n = (int)a.size();
ll m = (int)b.size();
if(n > m){
g << 0;
return 0;
}
PUTERE = 1;
for(ll i = 0;i < n;++i){
hashA = (hashA + a[i] * PUTERE) % MOD;
hashB = (hashB + b[i] * PUTERE) % MOD;
PUTERE = (PUTERE * PRIME) % MOD;
}
if(hashA == hashB && match(0))
sol.push_back(0);
b += " ";
for(ll i = n;i <= m;++i){
hashB = (hashB - b[i - n]) % MOD;
hashB /= PRIME;
hashB = (hashB + b[i] * PUTERE) % MOD;
while(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;
}