Pagini recente » Cod sursa (job #173971) | Cod sursa (job #619232) | Cod sursa (job #427239) | Cod sursa (job #121307) | Cod sursa (job #1519747)
#include <fstream>
#include <cstring>
#define MOD1 100007
#define MOD2 666013
#define P 73
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int Lmax = 2000010;
char str1[Lmax], str2[Lmax];
int potrivire[Lmax];
int N, M;
int str1b1, str1b2;
int str2b1, str2b2;
int putere1, putere2;
int nrmatchuri;
int main ()
{
f.get(str1, sizeof(str1));
f.get();
f.get(str2, sizeof(str2));
M = strlen(str1);
N = strlen(str2);
if(M > N) { g << '0' << '\n'; return 0;}
str1b1 = str1b2 = 0;
putere1 = putere2 = 1;
for(int i = 0; i < M; i ++)
{
str1b1 = (str1b1 * P + str1[i]) % MOD1;
str1b2 = (str1b2 * P + str1[i]) % MOD2;
if(i != 1)
{
putere1 = (putere1 * P) % MOD1;
putere2 = (putere2 * P) % MOD2;
}
}
str2b1 = str2b2 = 0;
nrmatchuri = 0;
for(int i = 0; i < M; i ++)
{
str2b1 = (str2b1 * P + str2[i]) % MOD1;
str2b2 = (str2b2 * P + str2[i]) % MOD2;
}
if(str1b1 == str2b1 && str1b2 == str2b2)
{
nrmatchuri += 1;
potrivire[0] = 1;
}
for(int i = M; i < N; i ++)
{
str2b1 = ((str2b1 - (str2[i - M] * putere1) % MOD1 + MOD1) * P + str2[i]) % MOD1;
str2b2 = ((str2b2 - (str2[i - M] * putere2) % MOD2 + MOD2) * P + str2[i]) % MOD2;
if(str1b1 == str2b1 && str1b2 == str2b2)
{
nrmatchuri += 1;
potrivire[i - M + 1] = 1;
}
}
g << nrmatchuri << '\n';
nrmatchuri = 0;
for(int i = 0; i < N && nrmatchuri < 1000; i ++) { if(potrivire[i]) g << i << ' '; nrmatchuri ++; }
g << '\n';
return 0;
}