Pagini recente » Cod sursa (job #2171553) | Cod sursa (job #2618833) | Cod sursa (job #2868792) | Cod sursa (job #1471018) | Cod sursa (job #2367526)
#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 && i >= 2 * sz ) {
if(pos.size() < 1000)
pos.push_back(i - 2 * sz);
ans ++;
}
}
out << ans << "\n";
for(auto it : pos)
out << it << " ";
return 0;
}