Cod sursa(job #2277246)

Utilizator ButmalaiDanButmalai Dan ButmalaiDan Data 5 noiembrie 2018 21:46:03
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include<fstream>
#include<string>
using namespace std;

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

int p[2000200]; 
int q = 0, ans = 0, ans_v[2000200];
string pattern, text;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    cin >> pattern >> text;
    text = ' ' + text;
    for(int i = 1; i <= text.size(); i++){
        while(q && text[i] != pattern[q]){
            q = p[q];
        }
       // for(int i = 0 ; i < text.size(); i++)
        //    cout << p[i] << " ";
        //cout << "\n";
        if(text[i] == pattern[q]){
            q++;
            if(q == pattern.size()){
                q = p[q];
                ans_v[ans] = i - pattern.size();
                ans++;
            }
        }
        p[i+1] = q;
    }
    cout << ans;
    cout << "\n";
    for(int i = 0 ; i < min(1000,ans); i++)
        cout << ans_v[i] << " ";
}