Pagini recente » Cod sursa (job #2870510) | Cod sursa (job #2623342) | Cod sursa (job #1814358) | Cod sursa (job #412082) | Cod sursa (job #2974188)
#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 LMAX = 2000001;
char a[LMAX], b[LMAX];
int pow[LMAX];
vector<int> r;
void add(int& hesh, int nr, int mod)
{
hesh = ((hesh*BASE)%mod + nr)%mod;
}
int main()
{
cin>>a>>b;
int n = strlen(a);
int m = strlen(b);
int hesh1 = 0;
int ah = 0;
pow[0] = 1;
for(int i=0; i<n; i++)
{
add(ah, a[i], MOD1);
add(hesh1, b[i], MOD1);
if(i)
pow[i] = (pow[i-1] * BASE) % int(1e9 + 7);
}
pow[n] = (pow[n-1] * BASE) % int(1e9 + 7);
int rez = 0;
if(hesh1 == ah)
{
rez++;
r.push_back(0);
}
for(int i=n; i<m && rez <= 1000; i++)
{
add(hesh1, b[i], MOD1);
hesh1 %= pow[n];
if(hesh1 == ah)
{
rez++;
r.push_back(i-n+1);
}
}
cout<<rez<<'\n';
for(int nr : r)
cout<<nr<<" ";
return 0;
}