Pagini recente » Cod sursa (job #2597853) | Cod sursa (job #933052) | Cod sursa (job #2134980) | Cod sursa (job #2304480) | Cod sursa (job #668099)
Cod sursa(job #668099)
#include<fstream>
#include<iostream>
#include<vector>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
#define baza 73
#define mod1 100007
#define mod2 100021
vector<int> matches;
string sir, subsir;
int hashSir1=0,hashSir2=0,hashSubsir1=0,hashSubsir2=0,baza_n1=1,baza_n2=1;
int main()
{
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
getline(fin,subsir);
getline(fin,sir);
//cerr<<sir<<'\n'<<subsir;
if (sir.size()<subsir.size())
{
fout<<0<<'\n';
return 0;
}
for(int i=0;i<subsir.length();++i)
{
hashSubsir1=(hashSubsir1*baza+subsir[i])%mod1;
hashSubsir2=(hashSubsir2*baza+subsir[i])%mod2;
hashSir1=(hashSir1*baza+sir[i])%mod1;
hashSir2=(hashSir2*baza+sir[i])%mod2;
if(i>0)
{
baza_n1=(baza_n1*baza)%mod1;
baza_n2=(baza_n2*baza)%mod2;
}
}
if(hashSir1==hashSubsir1 && hashSir2==hashSubsir2)
{
matches.push_back(1);
}
for(int i=subsir.length();i<sir.length();++i)
{
hashSir1=((hashSir1-(sir[i-subsir.length()]*baza_n1)%mod1+mod1)*baza + sir[i])%mod1;
hashSir2=((hashSir2-(sir[i-subsir.length()]*baza_n2)%mod2+mod2)*baza + sir[i])%mod2;
if(hashSir1==hashSubsir1 && hashSir2==hashSubsir2)
{
matches.push_back(i-subsir.length()+1);
}
}
fout<<matches.size()<<'\n';
for(int i=0;i<matches.size();++i)
{
fout<<matches[i]<<' ';
}
fout<<'\n';
fout.close();
return 0;
}