Pagini recente » Borderou de evaluare (job #423657) | Borderou de evaluare (job #890393) | Borderou de evaluare (job #2516858) | Borderou de evaluare (job #2065322) | Cod sursa (job #1800208)
#include <bits/stdc++.h>
using namespace std;
const int m1 = 100000007;
int h[2000001], b[2000001];
long long baza = 17;
long long cheie;
long long var;
int i, n, m, contor, raspuns[2000001];
char c[2000000], s[2000000];
int main()
{
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
fin.getline(c, 2000000);
fin.getline(s, 2000000);
for (i = strlen(c)-1; i>=0; --i)
cheie = (cheie*baza + c[i])%m1;
for (i = strlen(s)-1; i>=0; --i)
{
var = h[i+1]*baza +s[i];
h[i] = var%m1;
}
n = strlen(s);
m = strlen(c);
b[0] = 1;
for (i = 1; i<=n; ++i)
{
var = b[i-1]*baza;
b[i] = (var)%m1;
}
for (i = m-1; i < n; ++i)
{
var = h[i+1]*b[m]%m1;
var = (h[i-m+1] + m1 - var)%m1;
if (cheie == var)
{
raspuns[contor] = i-m+1;
++contor;
}
}
fout << contor << '\n';
for (i=0; i<contor; ++i)
fout << raspuns[i] << " ";
return 0;
}