Pagini recente » Cod sursa (job #2093987) | Cod sursa (job #2053890) | Cod sursa (job #47275) | Cod sursa (job #2051858) | Cod sursa (job #2079722)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int d = 26;
const int q = 666013;
int n, m;
string s1, s2;
vector < int > sol;
void find_pat() {
n = s1.size();
m = s2.size();
int h = 1, v1 = 0, v2 = 0;
for(int i = 0; i <= m - 2; i++) {
h = (h * d) % q;
}
for(int i = 0; i < m; i++) {
v1 = (d * v1 + s1[i]) % q;
v2 = (d * v2 + s2[i]) % q;
}
for(int i = 0; i <= n - m; i++) {
if(v1 == v2) {
int j;
for(j = 0; j < m; j++) {
if(s1[i + j] != s2[j])
break;
}
if(j == m)
sol.push_back(i);
}
if(i + m < n) {
v1 = (d * (v1 - s1[i] * h) + s1[i + m]) % q;
if(v1 < 0)
v1 += q;
}
}
}
int main()
{
in >> s2 >> s1;
find_pat();
out << sol.size() << '\n';
for(int i = 0; i < min(1000, (int)sol.size()); i++)
out << sol[i] << ' ';
in.close();
out.close();
return 0;
}