Pagini recente » Cod sursa (job #2680568) | Cod sursa (job #2794447) | Cod sursa (job #1881683) | Cod sursa (job #2503457) | Cod sursa (job #2976776)
#include<fstream>
#include<cstring>
#include<vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int BASE = 128;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1;
const int LMAX = 2000001;
char a[LMAX], b[LMAX];
uint64_t pow1[LMAX], pow2[LMAX];
vector<int> r;
void add(int& hesh, int nr, int mod)
{
hesh = ((1LL * hesh * BASE)%mod + nr)%mod;
}
int main()
{
cin>>a>>b;
int n = strlen(a);
int m = strlen(b);
int hesh1 = 0;
int hesh2 = 0;
int ah1 = 0;
int ah2 = 0;
pow1[0] = 1;
pow2[0] = 1;
for(int i=0; i<n; i++)
{
add(ah1, a[i], MOD1);
add(ah2, a[i], MOD2);
add(hesh1, b[i], MOD1);
add(hesh2, b[i], MOD2);
if(i)
{
pow1[i] = (pow1[i-1] * BASE) % MOD1;
pow2[i] = (pow2[i-1] * BASE) % MOD2;
}
}
int rez = 0;
if(hesh1 == ah1 && ah2 == hesh2)
{
rez++;
r.push_back(0);
}
for(int i=n; i<m; i++)
{
hesh1 -= (b[i-n]*pow1[n-1])%MOD1;
hesh2 -= (b[i-n]*pow2[n-1])%MOD2;
add(hesh1, b[i], MOD1);
add(hesh2, b[i], MOD2);
if(hesh1 == ah1 && ah2 == hesh2)
{
rez++;
r.push_back(i-n+1);
}
}
cout<<rez<<'\n';
for(int i=0; i<r.size() && i<1000; i++)
cout<<r[i]<<" ";
return 0;
}