Pagini recente » Cod sursa (job #1476519) | Cod sursa (job #842315) | Cod sursa (job #1526483) | Cod sursa (job #849804) | Cod sursa (job #1918558)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int nMax = 2000003;
const unsigned int Base = 97;
char a[nMax], b[nMax];
unsigned int Put[nMax], bhasuit[nMax];
inline unsigned int Decod(const int st,const int dr) {
return bhasuit[dr] - bhasuit[st - 1] * Put[dr - st + 1];
}
vector <int> ans;
int main()
{
unsigned int hs = 0;
f >> (a + 1);
f >> (b + 1);
int n = strlen(a + 1);
int m = strlen(b + 1);
int cnt = 0;
for(int i = 1; i <= n; i++) {
hs = hs * Base + a[i];
}
Put[0] = 1;
for(int i = 1; i <= m; i++) {
bhasuit[i] = bhasuit[i - 1] * Base + b[i];
Put[i] = Put[i - 1] * Base;
}
for(int i = n; i <= m; i++) {
if(Decod(i - n + 1, i) == hs) {
cnt++;
if(cnt <= 1000) {
ans.push_back(i - n);
}
}
}
g << cnt << "\n";
for(const auto &i : ans) {
g << i << " ";
}
return 0;
}