Pagini recente » Cod sursa (job #3319767) | Cod sursa (job #2447239) | Cod sursa (job #780496) | Cod sursa (job #487131) | Cod sursa (job #3333519)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int mod = 1e9+7, p = 65;
string a, b;
int n, m, cnt;
vector<int> poz(1002);
long long pattern, secv, pw = 1;
int main()
{
fin>>a>>b;
n = a.size();
m = b.size();
for(int i = 0; i < n; ++i)
{
pattern = (pattern * p + a[i]) % mod;
secv = (secv * p + b[i]) % mod;
if(i < n-1)
pw = pw * p % mod;
}
if(pattern == secv)
{
++cnt;
poz[cnt] = 0;
}
for(int i = n; i < m; ++i)
{
int st = i - n + 1;
secv = (secv - (b[st-1] * pw % mod) + mod) % mod;
secv = (secv * p + b[i]) % mod;
if(secv == pattern)
{
++cnt;
if(cnt <= 1000)
poz[cnt] = st;
}
}
fout<<cnt<<'\n';
for(int i = 1; i <= cnt && i <= 1000; ++i)
fout<<poz[i]<<' ';
return 0;
}