Pagini recente » Cod sursa (job #469783) | Cod sursa (job #321923) | Cod sursa (job #2163153) | Cod sursa (job #1018264) | Cod sursa (job #2696424)
#include <bits/stdc++.h>
using namespace std;
#define MOD1 100007
#define MOD2 100021
#define B 73
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a,b;
vector <int> sol;
int main()
{
fin >> a >> b;
int cod1=0, cod2=0, p1, p2, c1=0, c2=0, nr = 0, n= a.size();
cod1 = cod2 = 0;
p1 = p2 = 1;
for(unsigned int i = 0; i < a.size(); i++)
{
cod1 = (cod1*B % MOD1 + a[i]%MOD1)%MOD1;
cod2 = (cod2*B % MOD2 + a[i]%MOD2)%MOD2;
if(i != 0)
p1 = p1*B %MOD1, p2 = p2*B %MOD2;
}
for(unsigned int i = 0 ; i < b.size(); i++)
if(i < a.size())
{
c1 = (c1*B %MOD1 + b[i]%MOD1)%MOD1;
c2 = (c2*B %MOD2 + b[i]%MOD2)%MOD2;
}
else{
if(c1 == cod1 && c2 == cod2)
{nr++; if(nr <= 1000) sol.push_back(i-n);}
c1 = ((c1 + MOD1 - b[i-n]*p1%MOD1)*B%MOD1 + b[i])%MOD1;
c2 = ((c2 + MOD2 - b[i-n]*p2%MOD2)*B%MOD2 + b[i])%MOD2;
}
if(c1 == cod1 && c2 == cod2)
{
nr++;
if(nr <= 1000) sol.push_back(b.size()-n);
}
fout << nr <<'\n';
for(unsigned int i = 0; i < sol.size(); i++)
fout << sol[i] << " ";
return 0;
}