Pagini recente » Cod sursa (job #1306613) | Cod sursa (job #1770080) | Cod sursa (job #1213921) | Cod sursa (job #1210733) | Cod sursa (job #2284292)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long long int n1 = 3, m1 = 666013;
long long int n2 = 3, m2 = 666013;
long long int h1, h2, h3, h4;
int nr;
int indici[999999];
char c[2000005];
char s[2000005];
int main()
{
f.getline(c, 2000005);
f.getline(s, 2000005);
int k1 = strlen(c);
int k2 = strlen(s);
long long int putere1 = 1;
long long int putere2 = 1;
for (int i = k1-1; i >= 0; i--)
{
h1 = (h1 + c[i]*putere1)%m1;
h3 = (h3 + s[i]*putere1)%m1;
if (i > 0) putere1 = (putere1*n1)%m1;
h2 = (h2 + c[i]*putere2)%m2;
h4 = (h4 + s[i]*putere2)%m2;
if (i > 0) putere2 = (putere2*n2)%m2;
}
for (int i = k1+1; i < k2-k1+1; i++)
{
if (h1 == h3 && h2 == h4)
indici[nr++] = i;
h3 = ((h3 - s[i]*putere1)*n1+s[i+1])%m1;
h4 = ((h4 - s[i]*putere2)*n2+s[i+1])%m2;
}
g << nr << "\n";
for (int i = 0; i < nr; i++)
g << indici[i] << " ";
return 0;
}