Pagini recente » Cod sursa (job #2826703) | Cod sursa (job #2961733) | Cod sursa (job #64589) | Cod sursa (job #2493293) | Cod sursa (job #3286538)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int nmax = 2000000;
const long long digits = 71;
unsigned int pat_hash1;
unsigned long long pat_hash2;
unsigned int txt_hash1;
unsigned long long txt_hash2;
char pat[nmax + 3];
char txt[nmax + 3];
int nrs;
vector <int> sol;
int lg;
int main()
{
fin>>pat>>txt;
long long p1=1,p2=1;
for(int i=0; pat[i]; i++)
{
lg++;
pat_hash1 = pat_hash1*digits + pat[i];
pat_hash2 = pat_hash2*digits + pat[i];
if(i!=0)
{
p1=p1*digits;
p2=p2*digits;
}
}
for(int i=0; txt[i]; i++)
{
if(i>=lg)
{
txt_hash1 =txt_hash1 - p1 * txt[i-lg];
txt_hash2 =txt_hash2 - p2 * txt[i-lg];
}
txt_hash1 = txt_hash1*digits + txt[i];
txt_hash2 = txt_hash2*digits + txt[i];
if(i>=lg-1 && pat_hash1 == txt_hash1 && pat_hash2 == txt_hash2)
{
nrs++;
if(sol.size()<1000)
sol.push_back(i-lg+1);
}
}
fout<<nrs<<'\n';
for(auto& i : sol)
fout<<i<<' ';
}