Pagini recente » Cod sursa (job #574283) | Cod sursa (job #2964211) | Cod sursa (job #1779900) | Cod sursa (job #1699505) | Cod sursa (job #2570933)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int h = 71;
const int mod1 = 367;
const int mod2 = 251;
const int DIM = 2e6 + 7;
string a;
string b;
int pw1[DIM];
int pw2[DIM];
vector <int> rez;
int main()
{
in >> a;
in >> b;
int cnt = 0;
pw1[0] = 1;
pw2[0] = 1;
int n = a.size();
int m = b.size();
if(n > m)
{
out << 0;
return 0;
}
for(int i = 1; i < n; i++)
{
pw1[i] = (1ll * pw1[i - 1] * h) % mod1;
pw2[i] = (1ll * pw2[i - 1] * h) % mod2;
}
int Sm1 = 0;
int Sm2 = 0;
for(int i = 0; i < n; i++)
{
int nr = a[i] - '0';
Sm1 = (1ll * Sm1 + (1ll * nr * pw1[n - i - 1]) % mod1) % mod1;
Sm2 = (1ll * Sm2 + (1ll * nr * pw2[n - i - 1]) % mod2) % mod2;
}
int Sc1 = 0;
int Sc2 = 0;
for(int i = 0; i < n; i++)
{
int nr = b[i] - '0';
Sc1 = (1ll * Sc1 + (1ll * nr * pw1[n - i - 1]) % mod1) % mod1;
Sc2 = (1ll * Sc2 + (1ll * nr * pw2[n - i - 1]) % mod2) % mod2;
}
if(Sc1 == Sm1 && Sc2 == Sm2)
{
cnt++;
rez.push_back(0);
}
for(int i = n; i < m; i++)
{
int nr1 = b[i - n] - '0';
int nr2 = b[i] - '0';
Sc1 = ((((1ll * Sc1 - (1ll * pw1[n - 1] * nr1) % mod1 + mod1) % mod1 ) * h) % mod1 + nr2) % mod1;
Sc2 = ((((1ll * Sc2 - (1ll * pw2[n - 1] * nr1) % mod2 + mod2) % mod2 ) * h) % mod2 + nr2) % mod2;
if(Sc1 == Sm1 && Sc2 == Sm2)
{
cnt++;
if(cnt <= 1000)
rez.push_back(i - n + 1);
}
}
out << cnt<<'\n';
for(int i = 0; i < rez.size(); i++)
out << rez[i]<<" ";
return 0;
}