Pagini recente » Cod sursa (job #280159) | Cod sursa (job #2790918) | Cod sursa (job #2632057) | Cod sursa (job #1719301) | Cod sursa (job #1228732)
#include<fstream>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<string>
#include<list>
#define Nmax 2000001
#define MOD1 82549
#define MOD2 99871
#define B1 29
#define B2 101
using namespace std;
void read(char *A, char *B)
{
FILE*f = fopen("strmatch.in", "r");
fscanf(f, "%s %s", A, B);
fclose(f);
}
void write(const int &nr_sol, const list<int> &sol)
{
FILE*g = fopen("strmatch.out", "w");
fprintf(g, "%d\n", nr_sol);
for(auto it = sol.begin(); it != sol.end(); ++it)
fprintf(g, "%d ", *it);
fclose(g);
}
int main()
{
char A[Nmax], B[Nmax];
read(A, B);
int size_A = strlen(A);
int size_B = strlen(B);
int keyA1 = 0, keyA2 = 0, keyB1 = 0, keyB2 = 0, PB1 = 1, PB2 = 1;
list<int> sol;
for(int i=0; i < size_A;++i)
{
keyA1 = ((keyA1 * B1) + A[i])%MOD1;
keyA2 = ((keyA2 * B2) + A[i])%MOD2;
if(i != 0)
{
PB1 = (PB1 * B1)%MOD1;
PB2 = (PB2 * B2)%MOD2;
}
}
int nr_sol = 0;
for(int i=0; i < size_B; ++i)
{
if(i >= size_A)
{
keyB1 = (((keyB1 - PB1 * B[i-size_A]) % MOD1 + MOD1) * B1 + B[i]) % MOD1;
keyB2 = (((keyB2 - PB2 * B[i-size_A]) % MOD2 + MOD2) * B2 + B[i]) % MOD2;
}
else
{
keyB1 = ((keyB1 * B1) + B[i])%MOD1;
keyB2 = ((keyB2 * B2) + B[i])%MOD2;
}
if(keyB1 == keyA1 && keyB2 == keyA2)
{
if(nr_sol < 1000)
sol.push_back(i - size_A + 1);
++nr_sol;
}
}
write(nr_sol, sol);
return 0;
}