Pagini recente » Cod sursa (job #1238967) | Cod sursa (job #1538376) | Cod sursa (job #327025) | Cod sursa (job #388926) | Cod sursa (job #2672700)
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A,B;
long long baza = 79;
long long mod = 666773;
int cnt = 0;
int poz[1001];
int main()
{
string A,B;
f >> A >> B ;
long long hash_A = 0,hash_B = 0;
for ( long long i = 0; i <A.size(); ++i) {
hash_A = ((hash_A * baza)%mod + (A[i] -'A'+1) )%mod;
}
for ( long long i = 0; i < A.size(); ++i) {
hash_B = ((hash_B * baza)%mod + (B[i] -'A'+1) )%mod;
}
if(hash_A == hash_B) {
++cnt;
poz[cnt] = 0;
}
long long k = A.size();
long long powbaza[200001];
powbaza[0] = 1;
for ( long long i = 1; i <= k; ++i){
powbaza[i] = (powbaza[i-1] *baza)%mod;
}
for ( long long i = A.size(); i < B.size(); ++i) {
hash_B = (hash_B - (((B[i-k]-'A' + 1) * powbaza[k-1]) % mod) + mod)%mod;
hash_B = ((hash_B * baza)%mod + (B[i] -'A'+1) )%mod;
if(hash_B == hash_A) {
++cnt;
if(cnt <= 1000)
poz[cnt] = i-k+1;
}
}
g << cnt << "\n";
for ( int i= 1; i <= min(cnt,1000); ++i)
g << poz[i] << " ";
return 0;
}