Cod sursa(job #2040097)

Utilizator Alex18maiAlex Enache Alex18mai Data 15 octombrie 2017 13:40:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <vector>

using namespace std;

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

string s , one , two;
vector < int > kmp (4000100);
vector < int > pos;

void make_s(){
    cin>>one>>two;
    s += ' ';
    s += one;
    s += '#';
    s += two;
}

void solve(){

    int cont = 0;
    
    for (int i=2; i<s.size(); i++){
        int last = kmp[i-1];
        while (s[last + 1] != s[i] && last != 0){
            last = kmp[last];
        }
        if (s[last + 1] == s[i]){
            kmp[i] = last + 1;
            if (kmp[i] == one.size()){
                cont++;
                if (cont <= 1000){
                    pos.push_back(i - 2 * one.size() - 1);
                }
            }
        }
    }

    cout<<cont<<'\n';
    for (auto &x : pos){
        cout<<x<<" ";
    }
}

int main() {

    make_s();

    solve();

    return 0;
}