Pagini recente » Cod sursa (job #2242275) | Cod sursa (job #3142952)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout ("strmatch.out");
const int dim = 2e6 + 5;
const int MOD = 1e9 + 7;
const int BASE = 257;
char a[dim] , b[dim];
int ph[dim] , pow_base[dim] , n , m , hashS;
vector <int> M;
long long Power (int b , int e)
{
if(e == 0)
return 1LL;
else if(e % 2)
return (1LL * (b % MOD) * (Power(b , e - 1) % MOD)) % MOD;
else
{
long long p = Power(b , e / 2) % MOD;
return (1LL * p * p) % MOD;
}
}
int InvMod (int n)
{
return Power(n , MOD - 2);
}
inline int Min (int a , int b)
{
if(M.size() > 1000)
return 1000;
else
return M.size();
}
int HashSecv (int p)
{
long long x = (ph[p] - (p - n == 0 ? 0 : ph[p - n])) % MOD;
while(x < 0) x += MOD;
return (1LL * x % MOD * (InvMod(pow_base[p - n+1]) % MOD)) % MOD;
}
int main()
{
fin >> a >> b;
n = strlen(a);
m = strlen(b);
pow_base[0] = 1;
for(int i = 1 ; i < m ; ++i)
pow_base[i] = (1LL * (pow_base[i - 1] % MOD) * (BASE % MOD)) % MOD;
/// Hash-ul stringului in care voi cauta
ph[0] = (1LL * pow_base[0] *(int)(b[0])) % MOD;
for(int i = 1 ; i < m ; ++i)
ph[i] = ((ph[i - 1] % MOD) + 1LL * (pow_base[i] * (int)(b[i])) % MOD) % MOD;
/// Hash-ul stringului pe care il caut
for(int i = 0 ; i < n ; ++i)
hashS = (hashS % MOD + 1LL * (pow_base[i] * (int)(a[i])) % MOD) % MOD;
for(int i = n - 1 ; i < m ; ++i)
{
if(HashSecv(i) == hashS)
{
if(M.size() < 1000)
M.push_back(i - n + 1);
else
break;
}
}
if(M.size() > 1000)
fout << "1000\n";
else
fout << M.size() << '\n';
for(int i = 0 ; i < Min(M.size() , 1000) ; ++i)
fout << M[i] << " ";
}