Pagini recente » Diferente pentru problema/tetris2 intre reviziile 8 si 7 | Cod sursa (job #1344270) | Cod sursa (job #3142958)
#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 = 313;
char a[dim] , b[dim];
long long ph[dim] , pow_base[dim] , n , m;
long long hashS , hash1 , inv;
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;
}
}
long long InvMod (int n)
{
return Power(n , MOD - 2) % MOD;
}
inline int Min (int a , int b)
{
if(M.size() > 1000)
return 1000;
else
return M.size();
}
int main()
{
fin >> a >> b;
n = strlen(a);
m = strlen(b);
pow_base[0] = 1;
long long inv = InvMod(BASE);
for(int i = 1 ; i < n ; ++i)
pow_base[i] = (1LL * (pow_base[i - 1] % MOD) * (BASE % MOD)) % MOD;
/// Hash-ul stringului in care voi cauta
for(int i = 0 ; i < n ; ++i)
hash1 = (hash1 % MOD) + 1LL * (pow_base[i] * (int)(b[i])) % MOD;
/// Hash-ul stringului pe care il caut
for(int i = 0 ; i < n ; ++i)
hashS = (hashS % MOD + 1LL * (pow_base[i] % MOD * (int)(a[i])) % MOD) % MOD;
cout << hashS << endl;
for(int i = n - 1 ; i < m ; ++i)
{
cout << hash1 << " ";
if(hash1 == hashS)
{
if(M.size() < 1000)
M.push_back(i - n + 1);
else
break;
}
hash1 = (hash1 - (int)(b[i - n + 1])) % MOD;
while(hash1 < 0) hash1 += MOD;
hash1 = (hash1 * inv) % MOD;
hash1 = (hash1 % MOD + (1LL * pow_base[n - 1] * ((int)(b[i + 1]))) % MOD) % MOD;
}
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] << " ";
}