Pagini recente » Cod sursa (job #3363190) | Cod sursa (job #3363180) | Cod sursa (job #3363222) | Monitorul de evaluare | Cod sursa (job #3363165)
#include <fstream>
#include <string>
#include <cmath>
#include <vector>
#define int long long
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int B=67;
const int mod=1e9+7;
int h[2000001];
vector <int> rez;
int prec[2000001];
int expo(int a, int n) {
if(n == 0) {
return 1;
} else {
if(n % 2 == 1) {
return (a * expo(a, n - 1)) % mod;
} else {
int t = expo(a, n / 2);
return (t * t) % mod;
}
}
}
int get(int i,int j) {
return (h[j]-h[i-1])*(expo(expo(B,i-1),mod-2))%mod;
}
signed main() {
string s;
fin >> s;
int sum=0;
for (int i=0;i<s.length();i++) {
sum+=((s[i]-'A'+1)*expo(B,i))%mod;
sum%=mod;
}
string t;
fin >> t;
for (int i=0;i<t.length();i++) {
if (i>0) {
h[i]=h[i-1]+(t[i]-'A'+1)*expo(B,i-1)%mod;
}else {
h[i]=(t[i]-'A'+1)*expo(B,i-1)%mod;
}
}
for (int i=s.length()-1;i<s.length();i++) {
int sum1=get(i-s.length()+1,i);
if (sum1==sum) {
rez.push_back(i-s.length()+1);
}
}
fout << rez.size() << '\n';
for (int i=0;i<rez.size();i++) {
if (i>1000) {
break;
}else {
fout << rez[i] << ' ';
}
}
return 0;
}