Pagini recente » Cod sursa (job #1790621) | Cod sursa (job #2802563) | Cod sursa (job #1615627) | Cod sursa (job #2256664) | Cod sursa (job #2038779)
#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), putere = 1, baza = 197;
long long h_pat = 0, h_txt = 0, modulo = 1000000007;
for ( int i = 0; i < n; ++i )
{
h_pat = (h_pat * baza + pattern[i]) % modulo;
h_txt = (h_txt * baza + text[i]) % modulo;
if ( i > 0 )
putere = (putere * baza) % modulo;
}
for ( int i = 0; i < m - n; ++i )
{
int j;
if ( h_pat == h_txt )
{
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 = (baza * (h_txt - text[i] * putere) + text[i+n]) % modulo;
}
}
int main()
{
fin>>pattern;
fin>>text;
rabin_karp();
fout<<cnt<<'\n';
for ( auto x:rez )
fout<<x<<" ";
}