Pagini recente » Cod sursa (job #711149) | Cod sursa (job #1795971) | Cod sursa (job #1094447) | Cod sursa (job #949071) | Cod sursa (job #2045851)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("strmatch.in"); ofstream fout ("strmatch.out");
unsigned int x=71,ha,p[2000002],hb[2000002];
char a[2000002],b[2000002];
int nr,v[1002];
void rabin_karp()
{ int n=strlen(a),m=strlen(b);
for(int i=n-1;i>=0;--i) ha=ha*x+a[i];
for(int i=m-1;i>=0;--i) hb[i]=hb[i+1]*x+b[i];
p[0]=1;
for(int i=1;i<=m;++i) p[i]=p[i-1]*x;
for(int i=n-1;i<m;++i )
{ if(ha==hb[i-n+1]-hb[i+1]*p[n])
{ if(nr<1000) v[++nr]=i-n+1;}
}
}
int main()
{ f>>a>>b;
rabin_karp();
fout<<nr<<'\n';
for(int i=1;i<=nr;++i) fout<<v[i]<<" ";
fout.close(); return 0;
}
/*
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
vector <int> rez;
unsigned int putere[2000002], baza = 71, h_pat, h_txt[2000002];
char pattern[2000002], text[2000002];
int cnt;
void rabin_karp()
{
int n = strlen(pattern), m = strlen(text);
for ( int i = n-1; i >= 0; --i )
h_pat = (h_pat * baza + pattern[i]);
for ( int i = m-1; i >= 0; --i )
h_txt[i] = (h_txt[i+1] * baza + text[i]);
putere[0] = 1;
for ( int i = 1; i <= m; ++i )
putere[i] = (putere[i-1] * baza);
for ( int i = n-1; i < m; ++i )
{
if ( h_pat == h_txt[i-n+1] - (h_txt[i+1]*putere[n]) )
{
cnt++;
if ( cnt <= 1000 )
rez.push_back(i-n+1);
}
}
}
int main()
{
fin>>pattern;
fin>>text;
rabin_karp();
fout<<cnt<<'\n';
vector <int> :: iterator it=rez.begin(), sf=rez.end();
for(;it!=sf;++it) fout<<*it<<" ";
}
*/