Pagini recente » Cod sursa (job #1917856) | Cod sursa (job #1495740) | Cod sursa (job #2405917) | Cod sursa (job #2254344) | Cod sursa (job #3149120)
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("popcnt")
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int BAZA = 73;
const int MOD1 = 666013;
const int MOD2 = 666017;
string A, B;
int sizeA, hashA1, hashA2;
int sizeB, hashB1, hashB2, precalc1, precalc2;
int sol;
queue<int> output;
static inline int lgput(int a, int b, int MOD){
int sol = 1;
while(b != 0){
if(b & 1)
sol = (long long)sol * a % MOD;
a = (long long)a * a % MOD;
b >>= 1;
}
return sol;
}
int main (){
ios_base::sync_with_stdio(false);
fin.tie(nullptr), fout.tie(nullptr);
fin>>A>>B;
sizeA = (int)A.size();
sizeB = (int)B.size();
if(sizeA <= sizeB){
hashA1 = hashA2 = 0;
for(int i=0; i < sizeA; i++){
hashA1 = ((long long)hashA1 * BAZA % MOD1 + (A[i]-'A'+1)) % MOD1;
hashA2 = ((long long)hashA2 * BAZA % MOD2 + (A[i]-'A'+1)) % MOD2;
}
//cout<<hashA1<<" "<<hashA2<<"\n";
hashB1 = hashB2 = 0;
for(int i=0; i < sizeA-1; i++){
hashB1 = ((long long)hashB1 * BAZA % MOD1 + (B[i]-'A'+1)) % MOD1;
hashB2 = ((long long)hashB2 * BAZA % MOD2 + (B[i]-'A'+1)) % MOD2;
}
precalc1 = lgput(BAZA, sizeA-1, MOD1);
precalc2 = lgput(BAZA, sizeA-1, MOD2);
for(int i=sizeA-1; i < sizeB; i++){
hashB1 = ((long long)hashB1 * BAZA % MOD1 + (B[i]-'A'+1)) % MOD1;
hashB2 = ((long long)hashB2 * BAZA % MOD2 + (B[i]-'A'+1)) % MOD2;
//cout<<hashB1<<" "<<hashB2<<"\n";
if(hashB1 == hashA1 && hashB2 == hashA2){
sol++;
if(sol <= 1000)
output.push(i-sizeA+1);
}
//cout<<i-sizeA+1<<" -> "<<i<<"\n";
hashB1 = ((long long)hashB1 - (long long)(B[i-sizeA+1]-'A'+1) * precalc1 % MOD1 + MOD1) % MOD1;
hashB2 = ((long long)hashB2 - (long long)(B[i-sizeA+1]-'A'+1) * precalc2 % MOD2 + MOD2) % MOD2;
}
}
fout<<sol<<"\n";
while(!output.empty()){
fout<<output.front()<<" ";
output.pop();
}
return 0;
}