Pagini recente » Cod sursa (job #3000851) | Cod sursa (job #2892776) | Cod sursa (job #1177991) | Cod sursa (job #1402785) | Cod sursa (job #2793571)
#include <bits/stdc++.h>
#define mod 666013
#define baza 63
using namespace std;
int put = 1, v[2000001];
int makehash(string a)
{
int nr = 0, i;
for (i = 0; i < a.size(); i++)
{
if (a[i] >= 'a' && a[i] <= 'z')
nr = (nr * baza + a[i] - 'a' + 1) % mod;
else if (a[i] >= 'A' && a[i] <= 'Z')
nr = (nr * baza + a[i] - 'A' + 27) % mod;
else
nr = (nr * baza + a[i] - '0' + 53) % mod;
}
return nr;
}
int remove(int a, int i, string s)
{
if (s[i] >= 'a' && s[i] <= 'z')
a -= (s[i] - 'a' + 1) * put % mod;
else if (s[i] >= 'A' && s[i] <= 'Z')
a -= (s[i] - 'A' + 27) * put % mod;
else
a -= (s[i] - '0' + 53) * put % mod;
while (a < 0)
a += mod;
return a;
}
int add(int a, int i, string s)
{
a = a * baza % mod;
if (s[i] >= 'a' && s[i] <= 'z')
a = (a + s[i] - 'a' + 1) % mod;
else if (s[i] >= 'A' && s[i] <= 'Z')
a = (a + s[i] - 'A' + 27) % mod;
else
a = (a + s[i] - '0' + 53) % mod;
return a;
}
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string a, b;
int ha = 0, hb = 0, cnt = 0, i, p = 0;
cin >> a >> b;
ha = makehash(a);
hb = makehash(b.substr(0, a.size()));
for (i = 0; i < a.size() - 1; i++)
put = (put * baza) % mod;
if (hb == ha)
if (a == b.substr(0, a.size()))
v[p++] = 0;
for (i = 0; i < b.size() - a.size(); i++)
{
hb = remove(hb, i, b);
hb = add(hb, i + a.size(), b);
if (hb == ha)
if (a == b.substr(i + 1, a.size()))
v[p++] = i + 1;
}
cout << p << '\n';
for (i = 0; i < p; i++)
cout << v[i] << ' ';
return 0;
}