Pagini recente » Cod sursa (job #189946) | Cod sursa (job #1279158) | Cod sursa (job #1274564) | Cod sursa (job #2057366) | Cod sursa (job #2367598)
#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 = " " + haystack;
needle = " " + needle;
vector<int> kmp(needle.size(), 0);
int k = 0;
for(int i = 2; i < needle.size(); i ++) {
while(k > 0 && needle[k + 1] != needle[i])
k = kmp[k];
if(needle[k + 1] == needle[i])
k ++;
kmp[i] = k;
}
k = 0;
int sz = needle.size() - 1, ans = 0;
vector<int> pos;
for(int i = 1; i < haystack.size(); i ++) {
while(k > 0 && haystack[i] != needle[k + 1])
k = kmp[k];
if(needle[k + 1] == haystack[i])
k ++;
if(k == sz) {
k = kmp[k];
if(pos.size() < 1000)
pos.push_back(i - sz);
ans ++;
}
}
out << ans << "\n";
for(auto it : pos)
out << it << " ";
return 0;
}