Pagini recente » Cod sursa (job #2691019) | Cod sursa (job #1330736) | Cod sursa (job #1829153) | Cod sursa (job #1752887) | Cod sursa (job #3286528)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int nmax = 2000000;
const int mod1 = 1000000007;
const int mod2 = 666013;
const long long digits = 52;
long long pat_hash1;
long long pat_hash2;
long long txt_hash1;
long long txt_hash2;
char pat[nmax + 3];
char txt[nmax + 3];
int nrs;
vector <int> sol;
int lg;
int main()
{
fin>>pat>>txt;
long long p1=1,p2=1;
for(int i=0;pat[i];i++){
lg++;
long long dg = pat[i]-'A'+1;
pat_hash1 = (pat_hash1 + dg)*digits % mod1;
pat_hash2 = (pat_hash2 + dg)*digits % mod2;
p1=(p1*digits)%mod1;
p2=(p2*digits)%mod2;
}
for(int i=0;txt[i];i++)
{
if(i>=lg){
txt_hash1 =(txt_hash1 - p1 * (txt[i-lg]-'A'+1) + digits*mod1) %mod1;
txt_hash2 =(txt_hash2 - p2 * (txt[i-lg]-'A'+1) + digits*mod2) %mod2;
}
txt_hash1 = (txt_hash1 + (txt[i]-'A'+1))*digits % mod1;
txt_hash2 = (txt_hash2 + (txt[i]-'A'+1))*digits % mod2;
if(i>=lg-1 && pat_hash1 == txt_hash1 && pat_hash2 == txt_hash2){
nrs++;
if(sol.size()<1000)
sol.push_back(i-lg+1);
}
}
fout<<nrs<<'\n';
for(auto& i : sol)
fout<<i<<' ';
}