Pagini recente » Cod sursa (job #2868189) | Cod sursa (job #2151069) | Cod sursa (job #1470503) | Cod sursa (job #1179983) | Cod sursa (job #2536045)
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
long long n, m;
long long mod1, mod2;
string A, B;
vector<long long> v;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long long nr;
void RabinKarp()
{
long long amod1=0, amod2=0;
long long bmod1=0, bmod2=0;
for(long long i = 0; i < m; i++)
{
bmod1 = (long long)(bmod1 * 53 + (B[i]-'a'+1)) % mod1;
bmod2 = (long long)(bmod2 * 53 + (B[i]-'a'+1)) % mod2;
}
for(long long i = 0; i < m; i++)
{
amod1 = (long long)(amod1 * 53 + (A[i]-'a'+1)) % mod1;
amod2 = (long long)(amod2 * 53 + (A[i]-'a'+1)) % mod2;
}
if(amod1 == bmod1 && amod2 == bmod2)
{
nr++;
v.push_back(0);
}
long long p1=1;
for(long long i = 1; i < m; i++)
p1 = (long long)(p1 * 53) % mod1;
long long p2=1;
for(long long i = 1; i < m; i++)
p2 = (long long)(p2 * 53) % mod2;
for(long long i = m; i < n; i++)
{
amod1 = (long long)(((amod1 - p1 * (A[i - m]-'a'+1)) * 53 + (A[i]-'a'+1)) % mod1 + mod1) % mod1;
amod2 = (long long)(((amod2 - p2 * (A[i - m]-'a'+1)) * 53 + (A[i]-'a'+1)) % mod2 + mod2) % mod2;
if(amod1 == bmod1 && amod2 == bmod2)
{
nr++;
v.push_back(i);
if(nr == 1000)
break;
}
}
}
int main()
{
f>>B;
f>>A;
n = A.size();
m = B.size();
mod1 = 666013;
mod2 = 1000000007;
RabinKarp();
g<<nr<<endl;
for(long long i = 0; i < nr; i++)
g<<(v[i] - m + 1)<<" ";
}