Cod sursa(job #2277189)

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

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

int p[2000200];
int main(){
    string pattern, text;
    int q = 0, ans = 0, ans_v[2000200];
    cin >> pattern >> text;
    for(int i = 1; i <= text.size(); i++){
        while(q && text[i-1] != pattern[q+1]){
            q = p[q];
        }

        if(text[i-1] == pattern[q+1]){
            q++;
            if(q == pattern.size()-1){
                q = p[q];
                ans_v[ans] = i - pattern.size();
                ans++;
            }
        }
        p[i-1] = q;
    }
    cout << ans;
    cout << "\n";
    for(int i = 0 ; i < ans; i++)
        cout << ans_v[i] << " ";
}