Pagini recente » Cod sursa (job #2606097) | Cod sursa (job #1903059) | Cod sursa (job #2095915) | Cod sursa (job #586681) | Cod sursa (job #2518122)
#include <bits/stdc++.h>
#define NM 2000005
#define MOD int(1e9+9)
///single Hash
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int n, m;
long long p[NM], h[NM], hs, hs2, h2[NM], p2[NM];
char s[NM], t[NM];
vector<int> rez;
int main()
{
fin.getline(s, NM);
fin.getline(t, NM);
n = strlen(t);
m = strlen(s);
p[0] = p2[0] = 1;
for(int i=1; i<=n; i++)
p[i] = (long long)(p[i-1]*31)%MOD, p2[i] = (p2[i-1]*53)%MOD;
for(int i=0; i<n; i++)
h[i] = (((i>0)? h[i-1]: 0) + p[i]*(t[i]-'0'+1) %MOD)%MOD;
for(int i=0; i<n; i++)
h2[i] = (((i>0)? h2[i-1]: 0) + p2[i]*(t[i]-'0'+1) %MOD)%MOD;
for(int i=0; i<m; i++)
hs = (long long)(hs + p[i]*(s[i]-'0'+1))%MOD;
for(int i=0; i<m; i++)
hs2 = (long long)(hs2 + p2[i]*(s[i]-'0'+1))%MOD;
int nr = 0;
for(int i=m-1; i<n; i++)
if( ((hs*p[i-m+1])%MOD) == ((h[i]- ((i>=m)?h[i-m]:0)+MOD)%MOD) &&
((hs2*p2[i-m+1])%MOD) == ((h2[i]- ((i>=m)?h2[i-m]:0)+MOD)%MOD))
{
nr++;
if(nr<1000)
rez.push_back(i-m+1);
}
fout << nr << '\n';
nr = 0;
for(auto it:rez)
if(nr > 1000)
break;
else fout << it << ' ', nr++;
return 0;
}