Cod sursa(job #1856154)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 24 ianuarie 2017 16:27:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>
using namespace std;

char str[(int)4e6 + 10];
int pi[sizeof(str)], *match;

void build_pi(char *str, const int n){
    for(int i = 1, k = 0; i < n; ++i){
        while(str[k] != str[i] && k) k = pi[k-1];
        if(str[k] == str[i]) ++k;
        pi[i] = k; } }

int main(){
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f >> str;
    const int n = strlen(str);
    f >> (str+n+1);
    const int m = strlen(str+n+1);
    str[n] = '#';

    build_pi(str, n+m+1);

    int rez = 0;
    vector<int> pozs;
    for(int i = 0; i < m; ++i){
        if(pi[n+i+1] == n){
            ++rez;
            if(pozs.size() < 1000) pozs.push_back(i+1 - n); } }

    g << rez << '\n';
    for(const auto x : pozs){
        g << x << ' '; }

    return 0; }