Pagini recente » Cod sursa (job #1583460) | Cod sursa (job #1979897) | Cod sursa (job #2683376) | Cod sursa (job #370937) | Cod sursa (job #3256064)
#include <fstream>
#include <vector>
#include <unordered_map>
using namespace std;
const int NMAX = 2000000;
using ll = long long;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
unordered_map <char, int> umap;
int b1 = 67, MOD1 = 1e9 + 7, b2 = 71, MOD2 = 100076969;
ll prec1[NMAX + 2], prec2[NMAX + 2];
void init() {
///map
for(char i = 'A'; i <= 'Z'; i++)
umap[i] = i - 'A' + 1;
for(char i = 'a'; i <= 'z'; i++)
umap[i] = (i - 'a' + 1) + 26;
for(char i = '0'; i <= '9'; i++)
umap[i] = (i - '0' + 1) + 52;
prec1[0] = 1; prec2[0] = 1;
for(int i = 1; i <= NMAX; i++) {
prec1[i] = (prec1[i - 1] * b1) % MOD1;
prec2[i] = (prec2[i - 1] * b2) % MOD2;
}
}
int logexp(ll a, int n, int MOD) {
ll p = 1;
for(int k = 1; k <= n; k <<= 1) {
if((n & k))
p *= a;
a *= a;
p %= MOD;
a %= MOD;
}
return p;
}
struct HASH {
ll roll_hash1 = 0;
ll roll_hash2 = 0;
ll invb1 = logexp(b1, MOD1 - 2, MOD1);
ll invb2 = logexp(b2, MOD2 - 2, MOD2);
void add(int ch, int pos) {
roll_hash1 = (roll_hash1 + umap[ch] * prec1[pos]) % MOD1;
roll_hash2 = (roll_hash2 + umap[ch] * prec2[pos]) % MOD2;
}
void removee(int ch, int pos) {
//cout << roll_hash1 << " ";
roll_hash1 -= (umap[ch] * prec1[pos]);
if(roll_hash1 < 0)
roll_hash1 += MOD1;
//cout << roll_hash1 << " ";
roll_hash1 = (roll_hash1 * invb1) % MOD1;
//cout << roll_hash1 << " ";
roll_hash2 -= (umap[ch] * prec2[pos]);
if(roll_hash2 < 0)
roll_hash2 += MOD2;
roll_hash2 = (roll_hash2 * invb2) % MOD2;
}
};
bool check(HASH a, HASH b) {
if(a.roll_hash1 == b.roll_hash1 && a.roll_hash2 == b.roll_hash2)
return true;
return false;
}
vector <int> ans;
int main()
{
init();
string a, b;
cin >> a >> b;
HASH var1, var2;
if(a.size() > b.size()) {
cout << 0;
return 0;
}
for(int i = 0; i < a.size(); i++) {
var1.add(a[i], (i + 1));
var2.add(b[i], (i + 1));
}
//cout << var1.roll_hash1 << " " << var1.roll_hash2 << '\n';
//cout << var2.roll_hash1 << " " << var2.roll_hash2 << '\n';
int sizee = 0;
if(check(var1, var2)) {
sizee++;
ans.push_back(0);
}
for(int i = a.size(); i < b.size(); i++) {
//cout << i << '\n';
var2.removee(b[i - a.size()], 1);
var2.add(b[i], a.size());
//cout << var2.roll_hash1 << '\n';
//cout << var1.roll_hash1 << " " << var1.roll_hash2 << '\n';
//cout << var2.roll_hash1 << " " << var2.roll_hash2 << '\n';
if(check(var1, var2)) {
sizee++;
if(sizee < 1000)
ans.push_back(i - a.size() + 1);
}
}
cout << sizee << '\n';
for(auto x : ans)
cout << x << " ";
/*for(auto var : umap)
cout << var.first << " " << var.second << '\n';*/
return 0;
}