Pagini recente » Cod sursa (job #980263) | Cod sursa (job #1608579) | Cod sursa (job #939768) | Cod sursa (job #1939584) | Cod sursa (job #2774665)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int NMAX = 2e6 + 5;
const int baza = 29;
const int mod = 1000000007;
vector <int> v;
char a[NMAX], b[NMAX];
int n, m, ha = 0, hsb = 0, cnt;
int main()
{
in >> (a+1) >> (b+1);
n = strlen(a+1);
m = strlen(b+1);
int puterea = 1;
for ( int i = 1; i <= n-1; ++i)
puterea = (puterea * baza) % mod;
for ( int i =1; i <= n; ++i)
{
ha = ((1LL * ha * baza)%mod + (int)a[i])%mod;
}
for ( int i = 1; i <= n; ++i)
{
hsb= ((1LL * hsb * baza)%mod + (int)b[i])%mod;
}
if(ha ==hsb)
{
++cnt;
v.push_back(1);
}
int aux = hsb;
for ( int dr = n+1; dr <= m; ++dr)
{
int hb = (aux - ((1LL * (int)b[dr-n] *puterea)%mod) + mod)%mod;
hb = (1LL*hb * baza)%mod;
hb = (hb + (int)b[dr])%mod;
if(ha == hb)
{
++cnt;
if(v.size() <= 1000)
v.push_back(dr - n);
}
aux = hb;
}
out << cnt<<endl;
for(int i = 0; i < v.size(); ++i)
{
out<<v[i]<<" ";
}
}