Pagini recente » Cod sursa (job #1442207) | Cod sursa (job #908251) | Cod sursa (job #857628) | Cod sursa (job #2834432) | Cod sursa (job #1748086)
#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);
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; }
for(int i = 0; i < n; ++i){
bord[i] = i - bord[i] + 1; }
return bord; }
int main(){
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string pat, str;
f >> pat >> str;
auto shift = mk_kmp_shift(pat);
int i_str = 0, i_pat = 0;
int nr_match = 0;
vector<int> rez;
while(i_str < str.size()){
int j = 0;
while(j < pat.size() && pat[i_pat + j] == str[i_str + j]){
++j; }
if(j == pat.size()){
if(nr_match++ < 1000){
rez.push_back(i_str); } }
if(i_pat == 0){
++i_str; }
else{
i_str += shift[i_pat-1];
i_pat -= shift[i_pat-1]; } }
g << nr_match << '\n';
for(const auto x : rez){
g << x << ' '; }
return 0; }