Pagini recente » Cod sursa (job #2954600) | Cod sursa (job #1954574) | Cod sursa (job #1163175) | Cod sursa (job #769080) | Cod sursa (job #2207098)
/// Rabin - Karp
#include <fstream>
#include <cstring>
#include <ctype.h>
#include <vector>
#define ll int
using namespace std;
//typedef long long ll;
int const NM = 2000007 , mod = 100007 , mod2 = 100021;
char pat [NM] , v [NM];
vector <int> sol;
char const in [] = "strmatch.in";
char const out [] = "strmatch.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;
freopen (in , "r" , stdin);
freopen (out , "w" , stdout);
scanf ("%s\n%s" , (pat + 1) , (v + 1));
int n = strlen (pat + 1) ;
ll val = 0 , pw = 1 , val2 = 0 , val1 = 0 , val22 = 0 , pw2 = 1, z2;
for(i = n ; i >= 1 ; -- i)
{
val = (val + (code (pat [i]) * pw) % mod) % mod;
val1 = (val1 + (code (pat [i]) * pw2) % mod2) % mod2;
pw = pw * 62 % mod;
pw2 = pw2 * 62 % mod2;
}
int p1 , p2 ;
int m = strlen (v + 1);
pw = pw2 = 1;
ll z;
for(i = n ; i >= 1 ; -- i)
{
val2 = (val2 + code (v [i]) * pw) % mod;
val22 = (val22 + code (v [i]) * pw2) % mod2;
z = pw;
z2 = pw2;
pw = pw * 62 % mod;
pw2 = pw2 * 62 % mod2;
}
if(val == val2 && val1 == val22)
{
++ best;
sol . push_back (0);
}
for(p1 = 1 , p2 = n + 1 ; p2 <= m ; ++ p1 , ++ p2)
{
val2 = (((val2 + mod) - z * code (v [p1])) % mod * 62 % mod + code (v [p2])) % mod;
val22 = (((val22 + mod2) - z2 * code (v [p1])) % mod2 * 62 % mod2 + code (v [p2])) % mod2;
if(val == val2 && val1 == val22)
{
++ best ;
if(sol . size () < 1000)
sol . push_back (p1);
}
}
printf ("%d\n" , best);
int it;
for(it = 0 ; it < sol . size () ; ++ it)
printf ("%d " , sol [it]);
return 0;
}