Cod sursa(job #2251424)

Utilizator gabriel-mocioacaGabriel Mocioaca gabriel-mocioaca Data 1 octombrie 2018 16:40:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <string>
#include <vector>
#include <fstream>

using namespace std;

#define cout out
#define cin in

ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main(){
    string pattern, info;
    int n, m;
    int i, j;
    vector<int> pat;

    cin >> pattern >> info;
    n = pattern.size();
    m = info.size();
    pat.resize(n, 0);

    vector<int> sol;

    j = 0; i = 1;
    while (i < n){
        if(pattern[i] == pattern[j]){
            pat[i] = j + 1;
            i++; j++;
        }else{
            if(j != 0){
                j = pat[j - 1];
            }else{
                i++;
            }
        }
    }

    i = j = 0;

    while(i < m){
        if(info[i] == pattern[j]){
            if(j == n - 1){
                sol.push_back(i - n + 1);
                j = pat[j];
            }else{
                j++;
            }
            i++;
        }else{
            if(j != 0){
                j = pat[j - 1];
            }else{
                i++;
            }
        }
    }

    cout << sol.size() << '\n';
    for(auto it : sol)
        cout << it << ' ';

    return 0;
}