Pagini recente » Cod sursa (job #1104527) | Cod sursa (job #2178042) | Cod sursa (job #868365) | Cod sursa (job #2861783) | Cod sursa (job #2721305)
#include <iostream>
#include <fstream>
#include <vector>
const int baza = 27 * 2 + 10;
const int MOD1 = 1e9 + 7;
using namespace std;
const int MAXN = 2e6;
typedef long long ll;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
typedef long long ll;
string a,b;
ll putere[MAXN];
int ascii(char c){
return int(c - 'A' + 1);
}
int main()
{
in>>a>>b;
ll p = 1;
for(int i = 0; i < a.size(); i++){
putere[i] = p;
p = (p * baza) % MOD1;
}
ll hasha = 0;
for(int i = 0; i < a.size(); i++){
hasha = ((hasha * baza + ascii(a[i]) + MOD1)) % MOD1;
// cout<<hasha<<" "<<ascii(a[i])<<endl;
}
// cout<<hasha<<endl;
ll hashb = 0;
for(int i = 0; i < a.size(); i++){
hashb = ((hashb * baza + ascii(b[i]) + MOD1)) % MOD1;
}
vector<int>ap;
if(hasha == hashb){
ap.push_back(0);
}
for(int i = a.size(); i < b.size(); i++){
hashb = hashb - ascii(b[i - a.size()]) * putere[a.size() - 1];
hashb = (hashb * baza + ascii(b[i])) % MOD1;
hashb = (hashb + MOD1) % MOD1;
if(hasha == hashb)
ap.push_back(i - a.size() + 1);
}
out<<ap.size()<<'\n';
for(int i = 0; i < min(1000,int(ap.size())); i++)
out<<ap[i]<<" ";
return 0;
}