Pagini recente » Cod sursa (job #2330907) | Cod sursa (job #1894831) | Cod sursa (job #1169634) | Cod sursa (job #857356) | Cod sursa (job #3174019)
#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 val[150];
void genp(){
int i,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, hash_pre1 = 0, hash_pre2 = 0,p1 = 1, p2 = 1;
genp();
fin >> s;
fin.get();
fin >> ch;
sz = strlen(s);
n = strlen(ch);
for(i = 0; i < sz; i++){
hash1_s = (hash1_s * base + val[s[i]]) % mod1;
hash2_s = (hash2_s * base + val[s[i]]) % mod2;
hash_pre1 = (hash_pre1 * base + val[ch[i]]) % mod1;
hash_pre2 = (hash_pre2 * base + val[ch[i]]) % mod2;
if(i != 0){
p1 = (p1 * base) % mod1;
p2 = (p2 * base) % mod2;
}
}
if(hash1_s == hash_pre1 && hash2_s == hash_pre2){
k++;
rez.push_back(i - sz);
}
for(i = sz; i < n; i++){
hash_pre1 = 1LL * ((hash_pre1 - (val[ch[i - sz]] * p1) % mod1 + mod1) * base + val[ch[i]]) % mod1;
hash_pre2 = 1LL * ((hash_pre2 - (val[ch[i - sz]] * p2) % mod2 + mod2) * base + val[ch[i]]) % mod2;
if(hash1_s == hash_pre1 && hash2_s == hash_pre2){
k++;
rez.push_back(i - sz + 1);
}
}
fout << k << "\n";
for(auto x : rez) fout << x << " ";
return 0;
}