Pagini recente » Cod sursa (job #3249184) | Cod sursa (job #2258023) | Cod sursa (job #2550908) | Cod sursa (job #2231024) | Cod sursa (job #2041534)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
void solve(string s, vector < int > &kmp, int len) {
for (int i = 2; i < s.size(); i ++) {
int k = kmp[i - 1];
if (s[i] == s[k + 1]) {
kmp[i] = kmp[i - 1] + 1;
continue;
}
while (s[k + 1] != s[i]) {
k = kmp[k];
if (not k) {
break;
}
}
if (s[k + 1] == s[i]) {
kmp[i] = k + 1;
continue;
}
kmp[i] = 0;
}
vector < int > sol(1001);
int cnt = 0;
int index = 0;
for (int i = len + 1; i < s.size(); i ++) {
if (kmp[i] == len) {
if (index < 1000) {
sol[++ index] = i - 1 - (2 * len);
}
cnt ++;
}
}
cout << cnt << '\n';
for (int i = 1; i <= index; i ++) {
cout << sol[i] << ' ';
}
cout << '\n';
}
int main(int argc, char const *argv[]) {
string patt, s;
cin >> patt >> s;
int len = patt.size();
s = ' ' + patt + '#' + s;
vector < int > kmp(s.size() + 7);
solve(s, kmp, len);
}