Pagini recente » Cod sursa (job #1935219) | Cod sursa (job #2274681) | Cod sursa (job #2214427) | Cod sursa (job #1869156) | Cod sursa (job #2910685)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
long long x1, x2, y5, y2;
long long const m1 = 10e6 + 7;
long long const m2 = 10e6 + 3;
vector < int > v;
int main(){
fin >> a >> b;
long long p1 = 1, p2 = 1;
for(int i = 0; i < a.length(); i++){
if(i){
p1 = (p1 * 123) % m1;
p2 = (p2 * 123) % m2;
}
x1 = (x1 * 123 + a[i]) % m1;
x2 = (x2 * 123 + a[i]) % m2;
y5 = (y5 * 123 + b[i]) % m1;
y2 = (y2 * 123 + b[i]) % m2;
}
if(x1 == y5 && x2 == y2) v.push_back(0);
for(int i = 1; i < b.length() - a.length() + 1; i++){
y5 = (((y5 - ((b[i - 1]) * p1) % m1 + m1) % m1) * 123 + b[i + a.length() - 1]) % m1;
y2 = (((y2 - ((b[i - 1]) * p2) % m2 + m2) % m2) * 123 + b[i + a.length() - 1]) % m2;
if(x1 == y5 && x2 == y2) v.push_back(i);
}
fout << v.size() << '\n';
int s = v.size();
for(int i = 0; i < min(s, 1000); i++)
fout << v[i] << ' ';
}