Cod sursa(job #1987795)

Utilizator xtreme77Patrick Sava xtreme77 Data 31 mai 2017 23:50:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std ;

const int MAX = 2e6 ;

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

char sir [MAX * 2 + 15] ;

int main() {
    cin >> (sir + 1) ;
    int l = strlen (sir + 1) ;
    int keep = l ;
    sir [l + 1] = '#' ;
    cin >> (sir + l + 2) ;
    l = strlen (sir + 1) ;
    vector <int> p (l + 1) ;
    vector <int> positions ;
    int number = 0 ;
    for (int i = 2 ; i <= l ; ++ i) {
        int best = p [i - 1] ;
        while (best != 0 and sir [best + 1] != sir [i]) {
            best = p [best] ;
        }
        if (sir [best + 1] == sir [i]) {
            p[i] = best + 1;
            if (p [i] == keep) {
                if (number > 1000) ++ number ;
                else {
                    ++ number ;
                    positions.push_back(i - 2 * keep - 1) ;
                }
            }
        }
    }
    cout << number << '\n' ;
    for (auto x : positions) {
        cout << x << ' ' ;
    }
    return 0;
}