Pagini recente » Cod sursa (job #919127) | Cod sursa (job #651096) | Cod sursa (job #2784523) | Cod sursa (job #2070452) | Cod sursa (job #2367492)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <queue>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & -x)
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main() {
string needle, haystack;
in >> needle >> haystack;
haystack = " " + needle + haystack;
int sz = needle.size();
vector<int> kmp(haystack.size(), 0);
int k = 0, ans = 0;
vector<int> pos;
for(int i = 2; i < haystack.size(); i ++) {
while(k > 0 && haystack[k + 1] != haystack[i])
k = kmp[k];
if(haystack[k + 1] == haystack[i])
k ++;
kmp[i] = k;
if(kmp[i] >= sz && pos.size() < 1000) {
pos.push_back(i - 2 * sz);
ans ++;
}
}
out << ans << "\n";
for(auto it : pos)
out << it << " ";
return 0;
}