Pagini recente » Istoria paginii utilizator/maria_adriana | Istoria paginii runda/infoexpert | Statistici Baogh Roland Peter (sanyiraikkonen) | Profil oglindaoglinjoara | Cod sursa (job #2869964)
#include <fstream>
#include <cstring>
#define Mod1 666013
#define Mod2 10007
#define maxN 2000001
#define Baza 256
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
char s1[maxN], s2[maxN];
int Nr = 0;
int Poz[maxN];
void rabin_karp(char s1[], char s2[])
{
int l1 = strlen(s1), l2 = strlen(s2);
int Putere1 = 1, Putere2 = 1;
int h1 = 0, h2 = 0, h3 = 0, h4 = 0;
for(int i = 0; i < l1; i++)
{
if(i != 1){
Putere1 = (Putere1 * Baza) % Mod1;
Putere2 = (Putere2 * Baza) % Mod2;
}
h1 = (h1 * Baza + s1[i]) % Mod1;
h2 = (h2 * Baza + s1[i]) % Mod2;
h3 = (h3 * Baza + s2[i]) % Mod1;
h4 = (h4 * Baza + s2[i]) % Mod2;
}
for(int i = 0; i <= l2 - l1; i++)
{
if(h1 == h3 && h2 == h4){
Nr++;
Poz[Nr] = i;
}
h3 = ((h3 - (s2[i] * Putere1) % Mod1 + Mod1) * Baza + s2[i + l1]) % Mod1;
h4 = ((h4 - (s2[i] * Putere2) % Mod2 + Mod2) * Baza + s2[i + l1]) % Mod2;
}
}
int main()
{
cin.get(s1, maxN);
cin.get();
cin.get(s2, maxN);
rabin_karp(s1,s2);
cout<<Nr<<"\n";
for(int i = 1; i <= Nr && i<=1000; i++)
cout << Poz[i] << " ";
cin.close();
cout.close();
return 0;
}