Pagini recente » Cod sursa (job #491072) | Cod sursa (job #1551900) | Cod sursa (job #2297575) | Cod sursa (job #621899) | Cod sursa (job #2207019)
/// Rabin - Karp
#include <cstdio>
#include <cstring>
#include <ctype.h>
#include <vector>
using namespace std;
typedef long long ll;
ll const NM = 2e6 + 7 , mod = 666013;
char pat [NM] , v [NM];
vector <int> sol;
char const in [] = "strmatch.in";
char const out [] = "strmatch.out";
int code (char x)
{
if (isdigit (x))
return x - '0';
if(isalpha (x) && x <= 'Z')
return x - 'A' + 10;
return x - 'a' + 35;
}
int best;
int main()
{
FILE *cin , *cout;
cin = fopen (in , "r");
cout = fopen (out , "w");
int i;
fgets (pat + 1 , NM , cin);
fgets (v + 1 , NM , cin);
fclose (cin);
int n = strlen (pat + 1) ;
pat [n] = '\0';
-- n;
ll val = 0 , pw = 1 , val2 = 0;
for(i = n ; i >= 1 ; -- i)
{
val = 1LL * (val + 1LL * code (pat [i]) * pw % mod) % mod;
pw = pw * 62LL % mod;
}
int p1 , p2 ;
int m = strlen (v + 1);
v [m] = '\0';
-- m;
pw = 1;
ll z;
for(i = n ; i >= 1 ; -- i)
{
val2 = val2 + 1LL * code (v [i]) * pw;
val2 %= mod;
z = pw;
pw = pw * 62LL;
pw %= mod;
}
for(p1 = 1 , p2 = n ; p2 <= m + 1 ; ++ p1 , ++ p2)
{
if(val == val2)
{
++ best ;
if(sol . size () < 1000)
sol . push_back (p1 - 1);
}
val2 = 1LL * ((val2 + mod) - 1LL * (z * code (v [p1]) % mod));
val2 = val2 % mod;
val2 = 62LL * val2;
val2 %= mod;
val2 = 1LL * (val2 + code (v [p2 + 1]));
val2 %= mod;
}
fprintf (cout , "%d\n" , best );
int it;
for(it = 0 ; it < sol . size () ; ++ it)
fprintf (cout , "%d " , sol [it]);
fputs ("" , cout);
return 0;
}