Pagini recente » Cod sursa (job #638985) | Cod sursa (job #986664) | Monitorul de evaluare | Cod sursa (job #1542887) | Cod sursa (job #1784409)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define MOD 100103;
void strmatch(string A, string B){
vector<int> v;
int count = 0;
int p = 26, p1 = 1;
int hashA = 0, hashB = 0;
int sizeA = A.size(), sizeB = B.size();
for(int i = 0; i < sizeA; ++i){
hashA = (hashA * p + A[i]) % MOD;
hashB = (hashB * p + B[i]) % MOD;
if(i != 0){
p1 = (p1 * p) % MOD;
}
}
if(hashA == hashB){
v.push_back(0);
count++;
}
for(int i = sizeA; i < sizeB && count < 1001 ; ++i){
hashB = ((hashB - B[i-sizeA] * p1) * p + B[i]) % MOD;
if (hashB < 0) {
hashB += MOD;
}
if(hashB == hashA){
v.push_back(i-sizeA+1);
count++;
}
}
cout << count << endl;
for(int i = 0; i < count; ++i)
cout << v[i] << " ";
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out","w", stdout);
string A, B;
cin >> A >> B;
strmatch(A, B);
return 0;
}