Pagini recente » politic | Cod sursa (job #2987288) | Cod sursa (job #1647053) | Cod sursa (job #3292940) | Cod sursa (job #182225)
Cod sursa(job #182225)
#ifdef WIN32
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define MUL1 101
#define MUL2 107
#define MOD1 100007
#define MOD2 100021
char a[2000896], b[2000896];
int main()
{
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s %s", a, b);
int la = strlen(a), lb = strlen(b);
if (la > lb)
{
printf("0\n");
return 0;
}
int a1 = 0, a2 = 0;
int b1 = 0, b2 = 0;
int p1 = 1, p2 = 1;
for (int i = 0; i < la; i++)
{
a1 = (a1 * MUL1 + a[i]) % MOD1;
a2 = (a2 * MUL2 + a[i]) % MOD2;
b1 = (b1 * MUL1 + b[i]) % MOD1;
b2 = (b2 * MUL2 + b[i]) % MOD2;
if (i)
{
p1 = (p1 * MUL1) % MOD1;
p2 = (p2 * MUL2) % MOD2;
}
}
int s = 0;
vector<int> sol;
if (a1 == b1 && a2 == b2)
{
s++;
sol.push_back(0);
}
for (int i = la; i < lb; i++)
{
b1 = ((b1 - (b[i - la] * p1) % MOD1 + MOD1) * MUL1 + b[i]) % MOD1;
b2 = ((b2 - (b[i - la] * p2) % MOD2 + MOD2) * MUL2 + b[i]) % MOD2;
if (a1 == b1 && a2 == b2)
{
s++;
if (s <= 1000)
sol.push_back(i - la + 1);
}
}
if (sol.size() == 0)
printf("0\n");
else
{
printf("%d\n", s);
for (int i = 0; i < (int)sol.size(); i++)
printf("%d ", sol[i]);
printf("\n");
}
return 0;
}