Pagini recente » Cod sursa (job #2499409) | Cod sursa (job #8414) | Cod sursa (job #1036930) | Cod sursa (job #1332091) | Cod sursa (job #3159436)
#include <fstream>
#include <vector>
#include <cstring>
#define pb push_back
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int N = 2e6 + 5, mod = 1e9 + 7;
typedef long long ll;
ll n, hsh;
char c1[N], c2[N];
vector<int> ans;
int main()
{
in >> c1;
in >> c2;
const int ptr = strlen(c2) - strlen(c1);
const int lg = strlen(c1);
int p = 1;
for(int i=0; i<lg; i++) {
n += p * (c1[i] - 'A' + 1);
p *= 50;
if(n >= mod)
n %= mod;
if(p >= mod)
p %= mod;
}
p = 1;
for(int i=ptr; i<strlen(c2); i++) {
hsh += p * (c2[i] - 'A' + 1);
if(i < strlen(c2) - 1)
p *= 50;
if(hsh >= mod)
hsh %= mod;
if(p >= mod)
p %= mod;
}
if(hsh == n)
ans.pb(ptr);
for(int i=ptr-1; i>=0; i--) {
hsh = ((hsh - (c2[i+lg] - 'A' + 1) * p % mod) + mod) % mod;
hsh *= 50;
if(hsh >= mod)
hsh %= mod;
hsh += c2[i] - 'A' + 1;
if(hsh >= mod)
hsh %= mod;
if(hsh == n)
ans.pb(i);
}
out << ans.size() << '\n';
for(int i=ans.size()-1; i>=0; i--)
out << ans[i] << ' ';
return 0;
}