Pagini recente » Cod sursa (job #193428) | Cod sursa (job #1502608) | Cod sursa (job #2907024) | Cod sursa (job #1460554) | Cod sursa (job #3174006)
#include <bits/stdc++.h>
#define mod1 1000000007
#define mod2 1000000009
#define base 67
#define nmax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector <int> rez;
char s[nmax];
char ch[nmax];
int hash_pre1[nmax];
//int hash_pre2[nmax];
int p1[nmax];
//int p2[nmax];
int val[150];
void genp(){
int i;
p1[0] = 1;
//p2[0] = 1;
for(i = 1; i <= nmax; i++){
p1[i] = (1LL * p1[i - 1] * base) % mod1;
//p2[i] = (1LL * p2[i - 1] * base) % mod2;
}
int c = 65;
for(i = 1; i <= 26; i++){
val[c] = i;
c++;
}
c = 97;
for( ; i <= 52; i++){
val[c] = i;
c++;
}
c = 48;
for( ; i <= 62; i++){
val[c] = i;
c++;
}
}
int main()
{
int n,i,sz,k = 0;
long long hash1_s = 0, hash2_s = 0;
genp();
fin >> s;
fin.get();
fin >> ch;
sz = strlen(s);
n = strlen(ch);
for(i = 0; i < sz; i++){
hash1_s = (hash1_s + 1LL * val[s[i]] * p1[i]) % mod1;
//hash2_s = (hash2_s + 1LL * val[s[i]] * p2[i]) % mod2;
}
for(i = 0; i < n; i++){
hash_pre1[i + 1] = 1LL * (hash_pre1[i] + 1LL * val[ch[i]] * p1[i]) % mod1;
//hash_pre2[i + 1] = 1LL * (hash_pre2[i] + 1LL * val[ch[i]] * p2[i]) % mod2;
}
for(i = 0; i + sz - 1 < n; i++){
long long c_hash1 = (1LL * (hash_pre1[i + sz] + mod1 - hash_pre1[i])) % mod1;
//long long c_hash2 = (1LL * (hash_pre2[i + sz] + mod2 - hash_pre2[i])) % mod2;
if(c_hash1 == hash1_s * p1[i] % mod1 /*&& c_hash2 == hash2_s * p2[i] % mod2*/){
k++;
rez.push_back(i);
}
}
fout << k << "\n";
for(auto x : rez) fout << x << " ";
return 0;
}