Pagini recente » Cod sursa (job #2288265) | Cod sursa (job #2294642) | Cod sursa (job #2955371) | Cod sursa (job #2972675) | Cod sursa (job #2483855)
#include <iostream>
#include <fstream>
#include <string.h>
#include <algorithm>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int DIM = 2000005;
const long long cst1 = 100021;
const long long cst2 = 100007;
const int nr = 30;
char a[DIM];
char b[DIM];
long long power1[DIM];
long long power2[DIM];
int rez[DIM];
int main()
{
/*functia hash se face cu puterile nr de litere posibile din vector in cazul acesta sunt nr de litere mici si mari din alfabet englez adica 52 */
in >> a;
in >> b;
int K = 0;
power1[0] = 1;
power2[0] = 1;
int A = strlen(a);
for(int i = 1;i <= A;i++)
{
power1[i] = (power1[i - 1] % cst1 * nr )% cst1;
power2[i] = (power2[i - 1] % cst2 * nr )% cst2;
}
int B = strlen(b);
if(A > B)
{out << 0;
return 0;
}
long long S1 = 0;
long long S2 = 0;
long long val1 = 0;
long long val2 = 0;
for(int i = 0;i < A;i++)
{
val1 = (val1 + (power1[A - i - 1] * a[i]) % cst1) % cst1;
val2 = (val2 + (power2[A - i - 1] * a[i] % cst2)) % cst2;
S1 = (S1 + (power1[A - i - 1] * b[i]) % cst1) % cst1;
S2 = (S2 + (power2[A - i - 1] *b[i]) % cst2) % cst2;
}
if(S1 == val1 && S2 == val2)
{K++;
rez[K] = 0;
}
for(int i = 1; i <= B - A;i++)
{
S1 = (((S1 - power1[A - 1] * b[i-1]) % cst1 * nr )% cst1 + b[i + A - 1]) % cst1;
S2 = (((S2 - power2[A - 1] * b[i-1]) % cst2 * nr )% cst2 + b[i + A - 1]) % cst2;
if(S1 == val1 && S2 == val2)
{
K++;
rez[K] = i;
}
}
out << K<<"\n";
/* normal K ,in cazul asta e restrictie de 1000 de afisari*/
for(int i = 1; i <= min(1000,K); i++)
out << rez[i] <<" ";
return 0;
}