Cod sursa(job #2538079)

Utilizator theo2003Theodor Negrescu theo2003 Data 4 februarie 2020 12:53:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <string>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int positions[1000];
int pos_size = 0, hide = 0;
int prefix[2000000];
int main(){
    string pat, str;
    cin>>pat>>str;
    if(pat.size() > str.size()){
        cout<<"0\n";
        return 0;
    }

    prefix[0] = 0;
    for(int x = 1, p = 0;x<pat.size();x++){
        if(pat[x] == pat[p]){
            p++;
            prefix[x] = p;
        }else{
            if(p){
                while(p)
                    p = prefix[p - 1];
                prefix[x] = p;
            }else prefix[x] = 0;
        }
    }

    for(int x = 0, i = 0;x<str.size();){
        if(str[x + i] != pat[i]){
            if(i){
                x = x + i - prefix[i - 1];
                i = prefix[i - 1];
            }else x++;
        }else{
            i++;
            if(i == pat.size()){
                if(pos_size == 1000)
                    hide++;
                else
                positions[pos_size++] = x;
                x = x + i - prefix[i - 1];
                i = prefix[i - 1];
            }
        }
    }

    cout<<pos_size + hide<<'\n';
    for(int x = 0;x<pos_size;x++){
        cout<<positions[x]<<' ';
    }
    return 0;
}