Pagini recente » Cod sursa (job #698483) | Cod sursa (job #1839851) | Cod sursa (job #1299596) | Cod sursa (job #1702303) | Cod sursa (job #1748090)
#include <bits/stdc++.h>
using namespace std;
vector<int> mk_kmp_shift(const string& str){
const int n = str.size();
vector<int> bord(n, 0), strong_bord(n, 0);
for(int i = 1, k = 0; i < n; ++i){
for( ; k && str[k] != str[i]; k = bord[k-1]);
if(str[k] == str[i]){
++k; }
bord[i] = k;
strong_bord[i] = ((i != n-1 && str[k+1] == str[i+1]) ? strong_bord[k-1] : k); }
for(int i = 0; i < n; ++i){
strong_bord[i] = i - strong_bord[i] + 1; }
return strong_bord; }
int main(){
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string pat, str;
f >> pat >> str;
const int n = str.size(), m = pat.size();
auto shift = mk_kmp_shift(pat);
int i_str = 0, i_pat = 0;
int nr_match = 0;
vector<int> rez;
int j = 0;
while(i_str < n){
while(i_pat < m && pat[i_pat] == str[i_str]){
++i_pat, ++i_str; }
if(i_pat == m){
if(nr_match++ < 1000){
rez.push_back(i_str-m); } }
if(i_pat == 0){
++i_str; }
else{
i_pat -= shift[i_pat-1]; } }
g << nr_match << '\n';
for(const auto x : rez){
g << x << ' '; }
return 0; }