Pagini recente » Cod sursa (job #32912) | Cod sursa (job #1681396) | Cod sursa (job #3210430) | Cod sursa (job #925596) | Cod sursa (job #3249974)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const long long nmax = 2000005;
const long long b1 = 131;
const long long mod1 = 1e9 + 7, mod2 = 1e9 + 9;
char a[nmax], b[nmax]; long long numi;
vector<int> v;
long long codif(char a){
return a - 'A' + 1;
}
long long expo(long long a, long long b, long long t)
{
long long sol = 1;
while(b)
if(b % 2 == 0){
if(t == 1)
a = (1LL * a * a) % mod1;
else
a = (1LL * a * a) % mod2;
b /= 2;
}
else{
if(t == 1)
sol = (1LL * sol * a) % mod1;
else
sol = (1LL * sol * a) % mod2;
b --;
}
return sol;
}
int main()
{
f >> a >> b;
long long num1 = 0, num2 = 0;
for(long long i = 0; a[i]; i ++)
{
num1 = (1LL * num1 * b1) % mod1;
num1 = (num1 + codif(a[i])) % mod1;
num2 = (1LL * num2 * b1) % mod2;
num2 = (num2 + codif(a[i])) % mod2;
}
long long nr1 = 0, nr2 = 0, n = strlen(a);
for(long long i = 0; b[i]; i ++)
{
nr1 = (1LL * nr1 * b1) % mod1;
nr1 = (nr1 + codif(b[i])) % mod1;
if(i >= n)
nr1 = (nr1 - 1LL * codif(b[i - n]) * expo(b1, n, 1) + mod1) % mod1;
nr1 %= mod1;
nr2 = (1LL * nr2 * b1) % mod2;
nr2 = (nr2 + codif(b[i])) % mod2;
if(i >= n)
nr2 = (nr2 - 1LL * codif(b[i - n]) * expo(b1, n, 2) + mod2) % mod2;
nr2 %= mod2;
if(nr1 == num1 && nr2 == num2)
v.push_back(i - n + 1);
}
g << min((int)v.size(), 1000) << '\n';
for(int i = 0; i < min((int)v.size(), 1000); i ++)
g << v[i] << " ";
return 0;
}