Pagini recente » Istoria paginii runda/emag_2016-incepatori-4 | Cod sursa (job #2499080) | Cod sursa (job #2009020) | Istoria paginii runda/4xaja/clasament | Cod sursa (job #2040396)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
void solve(string &s, int len, vector < int > &Z) {
int index = 0;
int L = -1, R = -1;
vector < int > poz(1001);
Z[0] = len;
for (int i = 1; i < s.size(); i ++) {
if (i >= R) {
int cnt = 1;
while (s[i + cnt - 1] == s[cnt - 1]) {
cnt ++;
if (i + cnt - 1 > s.size()) {
break;
}
}
cnt --;
L = i;
Z[i] = cnt;
R = i + cnt - 1;
}
int k = Z[i - L];
if (i + k - 1 < R) {
Z[i] = k;
continue;
}
int cnt = R - i + 1;
while (s[i + cnt - 1] == s[cnt - 1]) {
cnt ++;
if (i + cnt - 1 > s.size()) {
break;
}
}
cnt --;
L = i;
Z[i] = cnt;
R = i + cnt - 1;
}
int sol = 0;
for (int i = len + 1; i < s.size(); i ++) {
if (Z[i] == len) {
sol ++;
if (index < 1000) {
poz[++ index] = i - len - 1;
}
}
}
cout << sol << '\n';
for (int i = 1; i <= index; i ++) {
cout << poz[i] << ' ';
}
cout << '\n';
}
int main(int argc, char const *argv[]) {
string pattern;
string s;
cin >> pattern >> s;
s = pattern + '#' + s;
vector < int > Z(s.size() + 7);
solve(s, pattern.size(), Z);
}