Pagini recente » Borderou de evaluare (job #2022198) | Cod sursa (job #468389) | Borderou de evaluare (job #1776952) | Cod sursa (job #2631800) | Cod sursa (job #1970429)
#include <bits/stdc++.h>
using namespace std;
#define FILE_IO
typedef pair<int, int> pii;
class RabinKarp
{
private:
int mod[2] = {(int)1e9 + 7, (int)1e9 + 9};
int base[2] = {137, 139};
string a, b;
public:
RabinKarp () {a = ""; b = "";}
RabinKarp (string _a, string _b) {a = _a; b = _b;}
vector<int> solve()
{
vector <int> ans;
ans.clear();
int N = a.size();
int M = b.size();
if(N > M) return ans;
pii hshA = {0, 0};
pii hshB = {0, 0};
pii pw = {1, 1};
for(int i = 0; i < N; i++)
{
char c;
c = a[i];
hshA.first = ((1LL * hshA.first * base[0]) % mod[0] + c) % mod[0];
hshA.second = ((1LL * hshA.second * base[1]) % mod[1] + c) % mod[1];
c = b[i];
hshB.first = ((1LL * hshB.first * base[0]) % mod[0] + c) % mod[0];
hshB.second = ((1LL * hshB.second * base[1]) % mod[1] + c) % mod[1];
pw.first = (1LL * pw.first * base[0]) % mod[0];
pw.second = (1LL * pw.second * base[1]) % mod[1];
}
if(hshA == hshB) ans.push_back(0);
for(int i = N; i < M; i++)
{
char c;
c = b[i];
hshB.first = ((1LL * hshB.first * base[0]) % mod[0] + c) % mod[0];
hshB.second = ((1LL * hshB.second * base[1]) % mod[1] + c) % mod[1];
c = b[i - N];
hshB.first = (hshB.first - (1LL * c * pw.first) % mod[0] + mod[0]) % mod[0];
hshB.second = (hshB.second - (1LL * c * pw.second) % mod[1] + mod[1]) % mod[1];
if(hshA == hshB) ans.push_back(i - N + 1);
}
return ans;
}
};
class KMP
{
private:
string a, b;
public:
KMP() {a = ""; b = "";}
KMP(string _a, string _b) {a = _a; b = _b;}
vector<int> solve()
{
vector <int> ans;
ans.clear();
int N = a.size();
int M = b.size();
if(N > M) return ans;
a.push_back(0);
vector <int> phi;
phi.resize(N + 5);
int l = 0;
for(int i = 1; i < N; i++)
{
while(l && a[l] != a[i])
l = phi[l - 1];
if(a[l] == a[i]) l++;
phi[i] = l;
}
l = 0;
for(int i = 0; i < M; i++)
{
while(l && a[l] != b[i])
l = phi[l - 1];
if(a[l] == b[i]) l++;
if(l >= N) ans.push_back(i - N + 1);
}
return ans;
}
};
class ZAlgo
{
private:
string a, b;
public:
ZAlgo() {a = ""; b = "";}
ZAlgo(string _a, string _b) {a = _a; b = _b;}
vector<int> solve()
{
vector <int> ans;
ans.clear();
int N = a.size();
int M = b.size();
if(N > M) return ans;
string c = a + b;
vector <int> z;
c.push_back(0);
z.resize((int)c.size() + 5);
int lst = 0, pmax = 0;
for(int i = 1; i < c.size(); i++)
{
if(pmax >= i)
z[i] = min(z[i - lst], pmax - i + 1);
z[i]++;
while(c[ z[i] - 1 ] == c[ i + z[i] - 1 ])
z[i]++;
z[i]--;
if(i + z[i] - 1 > pmax)
{
pmax = i + z[i] - 1;
lst = i;
}
if(i >= N && z[i] >= N)
ans.push_back(i - N);
}
return ans;
}
};
int main()
{
#ifdef FILE_IO
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
#endif
string a, b;
cin >> a >> b;
KMP kmp(a, b);
auto ans = kmp.solve();
printf("%d\n", ans.size());
for(int i = 0; i < ans.size() && i < 1000; i++)
printf("%d ", ans[i]);
return 0;
}