Pagini recente » Cod sursa (job #56980) | Cod sursa (job #426239) | Cod sursa (job #2998549) | Cod sursa (job #2016617) | Cod sursa (job #1506875)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2000000;
const int MOD1 = 104234;
const int MOD2 = 124923;
int N; int M;
char A[NMAX]; char B[NMAX];
vector<int> RabinKarp(char* A, char* B) {
vector<int> sol;
int p1 = 1; int p2 = 1;
int interval = 'z' - 'A' + 1;
int hashA1 = 0; int hashB1 = 0;
int hashA2 = 0; int hashB2 = 0;
for(int i = 0 ; i < N; ++i) {
hashA1 = (1LL * hashA1 * interval + 1LL * (A[i] - 'A') ) % MOD1;
hashA2 = (1LL * hashA2 * interval + 1LL * (A[i] - 'A') ) % MOD2;
if(i) {
p1 = 1LL * p1 * interval % MOD1;
p2 = 1LL * p2 * interval % MOD2;
}
}
if(N > M) {
sol.push_back(0);
return sol;
}
for(int i = 0; i < N; ++i) {
hashB1 = (1LL * hashB1 * interval + 1LL * (B[i] - 'A') ) % MOD1;
hashB2 = (1LL * hashB2 * interval + 1LL * (B[i] - 'A') ) % MOD2;
}
for(int i = N; i < M; ++i) {
if(hashB1 == hashA1 && hashA2 == hashB2 && sol.size() < 1000)
sol.push_back(i - N);
hashB1 = hashB1 - p1 * (B[i - N] - 'A');
hashB2 = hashB2 - p2 * (B[i - N] - 'A');
if(hashB1 < 0)
hashB1 += MOD1;
if(hashB2 < 0)
hashB2 += MOD2;
hashB1 = ( 1LL * hashB1 * interval + 1LL * (B[i] - 'A') ) % MOD1;
hashB2 = ( 1LL * hashB2 * interval + 1LL * (B[i] - 'A') ) % MOD2;
}
if(hashB1 == hashA1 && hashA2 == hashB2 && sol.size() < 1000)
sol.push_back(M - N);
return sol;
}
int main() {
fin >> A;
fin >> B;
N = strlen(A);
M = strlen(B);
vector<int> sol;
sol = RabinKarp(A, B);
fout << sol.size() << '\n';
for(unsigned i = 0 ; i < sol.size(); ++i)
fout << sol[i] << " " ;
return 0;
}