Pagini recente » Cod sursa (job #3281145) | Cod sursa (job #1307633) | Cod sursa (job #1152352) | Cod sursa (job #1373987) | Cod sursa (job #2207024)
/// Rabin - Karp
#include <fstream>
#include <cstring>
#include <ctype.h>
#include <vector>
using namespace std;
typedef long long ll;
ll const NM = 2000007 , mod = 1000003;
char pat [NM] , v [NM];
vector <int> sol;
char const in [] = "strmatch.in";
char const out [] = "strmatch.out";
ifstream cin (in);
ofstream cout (out);
inline int code (char x)
{
if (isdigit (x))
return x - '0';
if(isalpha (x) && x <= 'Z')
return x - 'A' + 10;
return x - 'a' + 36;
}
int best;
int main()
{
int i;
cin >> pat + 1 >> v + 1;
cin . close ();
int n = strlen (pat + 1) ;
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);
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;
}
cout << best << '\n';
int it;
for(it = 0 ; it < sol . size () ; ++ it)
cout << sol [it] << ' ';
return 0;
}