Cod sursa(job #2709298)

Utilizator Casian_doispeChiriac Casian Casian_doispe Data 20 februarie 2021 10:06:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.64 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <climits>
#include <queue>

#define MOD 666013

using namespace std;

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

/// string matching folosind strstr(), nu kmp sau alte vrajeli
/// pt majoritatea cazurilor putem face pur si simplu strstr si apoi mergem de la elem urm indicat de pointer si cautam urm aparitie, pe infoarena asta ia vreo 96 pct daca nar avea ei sistemul ala retard
/// pt eficienta identica cu kmp este necesara o optimizare foarte complicata care nu se merita de obicei :
/// se afla cat de mult se suprapune stringul de cautat cu el insusi, de ex daca il gasim pe aabaaa in b atunci mai trebuie doar sa cautam daca exista un baaa dupa aabaaa -ul gasit, si daca se tot intampla sa existe
/// continuam asa, deci nu trecem niciodata de doua ori prin aceleasi char-uri, in rest daca nu exista folosim strstr sa gasim urm aparitie a lui a in b

vector<int> v ;

int process(string a) /// determinam indicele pana la care se suprapune a cu el insusi de ex pt stringul casian k = a.size() deci se pot lipi unul in spatele altuia, dar pt aaabaaa k = 4, adica se poate avea :
                      /// aaabaaabaaa si aici apare aaabaaa de doua ori
{

    int k = 0 ;

    for(int f = a.size() - 1 ; f >= 0 ; f --)
    {

        /// dau match la primele f caract si ultimele f caract

        string st = a.substr(0, f) ;
        string dr = a.substr(a.size() - f, a.size()) ;

        if(st == dr)return a.size() - f ;

    }

    return a.size() ;

}

int main()
{

    string a, b ;

    cin >> a >> b ;

    int k = process(a) ;

    string remainder = a.substr(a.size() - k, a.size() - k + a.size() - k) ; /// pe asta il cautam de la capat, daca este prezent acolo atunci continuam altfel doar cautam de la capat tot striungul

    char *ptr = &b[0], *auxptr ;

    while(auxptr = strstr(ptr, &a[0]))
    {

        v.push_back(auxptr - &b[0]) ;

        /// lam gasit pe a in auxptr
        /// acuma trebe sa vedem daca la sfarsitul lui a se afla remainder

        int poz = auxptr - &b[0] + a.size() ;

        while(remainder.size() && b.substr(poz, remainder.size()) == remainder)
        {

            poz += remainder.size() ; /// poz devine sfarsitul lui remainder

            v.push_back(poz - a.size()) ;

        }

        ptr = &b[poz - 1] ;

    }

    cout << v.size() << endl ;

    for(int f = 0 ; f < v.size() && f < 1000 ; f ++)
        cout << v[f] << " " ;

    return 0 ;
}