Cod sursa(job #2469585)

Utilizator AnduebossAlexandru Ariton Andueboss Data 7 octombrie 2019 18:55:11
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
//
//  main.cpp
//  ZAlgorithm
//
//  Created by Andu Andu on 30/09/2019.
//  Copyright © 2019 Andu Andu. All rights reserved.
//

#include <string>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cmath>
#define ll long long

using namespace std;

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

void getZarray(string str, ll Z[]) {
    ll n = str.length();
    ll L, R, k;
    L=R=0;
    for(ll i=1;i<n;i++) {
        if (i > R) {
            L=R=i;
            while ( R<n && str[R-L] == str[R]) {
                R++;
            }
            Z[i] = R-L;
            R--;
        } else {
            k = i-L;
            if(Z[k] < R-i+1) {
                Z[i] = Z[k];
            } else {
                L = i;
                while ( R<n && str[R-L] == str[R]) {
                    R++;
                }
                Z[i] = R-L;
                R--;
            }
        }
    }
}

vector<ll> indexes;

void searchFor(string text, string pattern) {
    string concat = pattern + "$" + text;
    ll l = concat.length();
    ll Z[l];
    getZarray(concat, Z);
    for ( ll i=0;i<l;i++) {
        if (Z[i] == pattern.length()) {
            //cout<<"pattern at index: "<< i-pattern.length() - 1<<"\n";
            indexes.push_back(i-pattern.length() - 1);
        }
    }
}

int main() {
    string text;// = "CABBCABABAB";
    string pattern;// = "ABA";
    cin>>pattern>>text;
    searchFor(text, pattern);
    cout<<indexes.size()<<"\n";
    ll len;
    if (indexes.size() > 1000) {
        len = 999;
    } else {
        len = indexes.size();
    }
    for(ll i=0;i<=len - 1;i++) {
        cout<<indexes[i]<<" ";
    }
    return 0;
}