Cod sursa(job #2759313)

Utilizator lahayonTester lahayon Data 16 iunie 2021 19:31:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>	
#include <string>
#include <vector>


using namespace std;



int main(){

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

    string A, B;
    cin >> A;
    cin >> B;

    vector<int> lps(A.length(), 0);
    for(int i = 1, len = 0; i < A.length();){

        if(A[i] == A[len]){
            ++len;
            lps[i] = len;
            ++i;
        }
        else if(len > 0)
            len = lps[len - 1];
        else{
            lps[i] = 0;
            ++i;
        }
      
    }
    vector<int> result;

    for(int i = 0, j = 0; i < B.length();){
       if(A[j] == B[i]){
           ++i;
           ++j;
       }
       if(j == A.length()){
           result.push_back(i - j);
           j = lps[j - 1];
       }
       else if(i < B.length() && A[j] != B[i]){
           if(j > 0)
                j = lps[j - 1];
            else ++i;
       }
    }

    cout << result.size() << "\n";
    for(int i = 0; i < result.size() && i < 1000; ++i)
        cout << result[i] << " ";

    cin.close();
    cout.close();


    return 0;	
}