Pagini recente » Cod sursa (job #228443) | Cod sursa (job #691893) | Cod sursa (job #2548513) | Cod sursa (job #568741) | Cod sursa (job #2041046)
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
vector <int> rez;
char pattern[2000000], text[2000000];
int cnt;
void rabin_karp()
{
int n = strlen(pattern), m = strlen(text), baza = 197;
long long h_pat_1 = 0, h_txt_1 = 0, modulo_1 = 1000000007, modulo_2 = 999999937, putere_1 = 1, putere_2 = 1, h_pat_2 = 0, h_txt_2 = 0;
for ( int i = 0; i < n; ++i )
{
h_pat_1 = (h_pat_1 * baza + pattern[i]) % modulo_1;
h_pat_2 = (h_pat_2 * baza + pattern[i]) % modulo_2;
h_txt_1 = (h_txt_1 * baza + text[i]) % modulo_1;
h_txt_2 = (h_txt_2 * baza + text[i]) % modulo_2;
if ( i > 0 )
{
putere_1 = (putere_1 * baza) % modulo_1;
putere_2 = (putere_2 * baza) % modulo_2;
}
}
for ( int i = 0; i < m - n; ++i )
{
int j;
if ( h_pat_1 == h_txt_1 && h_pat_2 == h_txt_2 )
{
for ( j = 0; j < n; ++j )
if ( text[j+i] != pattern[j] )
break;
if ( j == n)
{
cnt++;
if ( cnt <= 1000)
rez.push_back(i);
}
}
if ( i < m - n )
{ h_txt_1 = (baza * (h_txt_1 - text[i] * putere_1) + text[i+n]) % modulo_1;
h_txt_2 = (baza * (h_txt_2 - text[i] * putere_2) + text[i+n]) % modulo_2;
if ( h_txt_1 < 0 )
h_txt_1 += modulo_1;
if ( h_txt_2 < 0 )
h_txt_2 += modulo_2;
}
}
}
int main()
{
fin>>pattern;
fin>>text;
rabin_karp();
fout<<cnt<<'\n';
for ( auto x:rez )
fout<<x<<" ";
}