Pagini recente » Cod sursa (job #698715) | Cod sursa (job #184893) | Cod sursa (job #1544995) | Cod sursa (job #2112773) | Cod sursa (job #2684548)
//#include <unordered_map>
//#include <vector>
#include <stdio.h>
#include <cstring>
#define NMax 2000001
#define MOD1 100007
#define MOD2 100011
#define min(a, b) ((a < b) ? a : b)
using namespace std;
char A[NMax], B[NMax];
//unordered_map<char, int> map;
/*
void initializeMap()
{
map['0'] = 0; map['1'] = 1; map['2'] = 2; map['3'] = 3;
map['4'] = 4; map['5'] = 5; map['6'] = 6; map['7'] = 7;
map['8'] = 8; map['9'] = 9;
map['a'] = 10; map['b'] = 11; map['c'] = 12; map['d'] = 13;
map['e'] = 14; map['f'] = 15; map['g'] = 16; map['h'] = 17;
map['i'] = 18; map['j'] = 19; map['k'] = 20; map['l'] = 21;
map['m'] = 22; map['n'] = 23; map['o'] = 24; map['p'] = 25;
map['q'] = 26; map['r'] = 27; map['s'] = 28; map['t'] = 29;
map['u'] = 30; map['v'] = 31; map['w'] = 32; map['x'] = 33;
map['y'] = 34; map['z'] = 35; map['A'] = 36; map['B'] = 37;
map['C'] = 38; map['D'] = 39; map['E'] = 40; map['F'] = 41;
map['G'] = 42; map['H'] = 43; map['I'] = 44; map['J'] = 45;
map['K'] = 46; map['L'] = 47; map['M'] = 48; map['N'] = 49;
map['O'] = 50; map['P'] = 51; map['Q'] = 52; map['R'] = 53;
map['S'] = 54; map['T'] = 55; map['U'] = 56; map['V'] = 57;
map['W'] = 58; map['X'] = 59; map['Y'] = 60; map['Z'] = 61;
}
*/
int main()
{
int result[1000];
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s %s", A, B);
int M = strlen(A);
int N = strlen(B);
//initializeMap();
int p = 1, p2 = 1, n = 0;
int aVal = 0;
int aVal2 = 0;
if (M > N)
{
printf("0\n");
return 0;
}
int hash1 = 0;
int hash2 = 0;
for (int i = 0; i < M; i++)
{
aVal = (aVal * 73 + A[i]) % MOD1;
aVal2 = (aVal2 * 73 + A[i]) % MOD2;
hash1 = (hash1 * 73 + B[i]) % MOD1;
hash2 = (hash2 * 73 + B[i]) % MOD2;
if (i != 0)
{
p = (p * 73) % MOD1;
p2 = (p2 * 73) % MOD2;
}
}
if (hash1 == aVal && hash2 == aVal2)
{
n++;
result[0] = 0;
}
for (int i = M; i < N; i++)
{
hash1 = ((hash1 - (B[i - M] * p) % MOD1 + MOD1) * 73 + B[i]) % MOD1;
hash2 = ((hash2 - (B[i - M] * p2) % MOD2 + MOD2) * 73 + B[i]) % MOD2;
if (hash1 == aVal && hash2 == aVal2)
{
if(n < 1000)
result[n] = (i - M + 1);
n++;
}
}
printf("%d\n", n);
for (int i = 0; i < min(n,1000); i++)
{
printf("%d ", result[i]);
}
return 0;
}