Cod sursa(job #2803421)

Utilizator dana24hdDana N dana24hd Data 19 noiembrie 2021 23:32:57
Problema Potrivirea sirurilor Scor 28
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>

using namespace std;

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

/**
KMP[i] = lung celui mai lung prefix care este si sufix
**/

vector <int> KMP(string s){

    s= "$"+s; /// adaugam un caracter

    vector<int> pi( s.size() );

    int k=0; /// k=pi[i-1]

    for(int i=2; i<(int)s.size(); i++){
        /// caz ideal s[i]==s[k+1]
        while( k!=0 && s[i]!=s[k+1] ){
            k=pi[k];
        }
        /// am gasit un match
        if( s[i]==s[k+1] )
            k++;

        /// daca nu am gasit match => conform while k=0

        pi[i]=k;
    }

    /// reindexam de la 0
    pi.erase( pi.begin() );

    return pi;

}

/**
Gaseste inceputul matchurilor lui s in t
s="abab"
t="ababcababab"

sol={ 0, 5, 7 };
**/

vector <int> FindMatches(string s, string t){

    string to_kmp=s+"$"+t;
    vector <int> kmp=KMP(to_kmp);

    vector <int> ans;

    for(int i=(int)s.size()+1; i<(int)kmp.size(); i++ ){
        if( kmp[i]==(int)s.size() )
            ans.push_back(i-2*(int)s.size());
    }
    return ans;
}

int main()
{

    string s, t;
    in>>s>>t;

    vector <int> pi = FindMatches(s, t);

    out<<(int)pi.size()<<'\n';

    for( auto i:pi ){
        if( i<1001 )
            out<<i<<" ";
    }


    //for( auto i:pi)
        //cout<<i;



    return 0;
}