Pagini recente » Cod sursa (job #619834) | Cod sursa (job #3202683) | Cod sursa (job #48681) | Cod sursa (job #2199142) | Cod sursa (job #2910115)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
int x1, x2, y5, y2;
long long const m1 = 10e9 + 7;
long long const m2 = 10e9 + 3;
vector<int> v;
int main(){
fin >> a >> b;
int p1 =1 , p2 = 1;
for(int i = 0; i < a.length(); i++){
if(i){
p1 = (p1 * 26) % m1;
p2 = (p2 * 26) % m2;
}
x1 = (x1 * 26 + a[i] - 'A') % m1;
x2 = (x2 * 26 + a[i] - 'A') % m2;
y5 = (y5 * 26 + b[i] - 'A') % m1;
y2 = (y2 * 26 + b[i] - 'A') % 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]- 'A') * p1) % m1 + m1) % m1) * 26 + b[i + a.length() - 1] - 'A' ) % m1;
y2 = (((y2 - ((b[i - 1]- 'A') * p2) % m2 + m2) % m2) * 26 + b[i + a.length() - 1] - 'A' ) % 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] << " ";
}