Cod sursa(job #2279131)

Utilizator ButmalaiDanButmalai Dan ButmalaiDan Data 8 noiembrie 2018 22:37:52
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include<fstream>
#include<string>
#include<vector> 

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    string pattern, text;

    cin >> pattern >> text;
    int ans = 0;
    int* pi  = new int[pattern.size()]();    
    fill_n(pi, pattern.size(), 0);
    vector<int> ans_vec;
    for(int i = 1,j = 0;i < pattern.size();i++){
        while(j && pattern[i] != pattern[j] ){
            j = pi[j-1];
        }
        if(pattern[i] == pattern[j]){
            j++;
        }
        pi[i] = j;
    }

     for(int i = 0,j = 0;i < text.size();i++){
        while(j && text[i] != pattern[j] ){
            j = pi[j-1];
        }
        if(text[i] == pattern[j]){
            j++;
        }
        if(j > pattern.size() - 1){
            ans++;
            ans_vec.push_back(i - pattern.size() + 1);
            j = pi[j-1];
        }
        pi[j] = j;
        //cout << text[i] << " " <<  pattern[j]  << " " << j << "\n";
    }
    cout << ans << "\n";
    for(int i = 0 ; i < min(int(ans_vec.size()),1000); i++){
        cout << ans_vec[i] << " ";
    }
}