Cod sursa(job #2909451)

Utilizator test9265test9265 test9265 Data 13 iunie 2022 19:02:46
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <string>
#include <vector>
#include <fstream>

using namespace std;

int main()
{
    ifstream fin;   fin.open("strmatch.in");
    ofstream fout;   fout.open("strmatch.out");
    string A, B;
    fin >> A >> B;
    
    int count, i, j;
    vector <int> vec(A.length(), 0);
    vector <int> rs;
    
    for (i=0, j=1; j<A.length(); j++)
    {
        if (A[i]!=A[j]) vec[j]=0;
        else{
            vec[j]=i+1;
            i++;
        }
    }
    
    for (i=0, j=0;i<B.length();)
    {
        if (B[i]==A[j])
        {
            i++;
            j++;
            if (j==A.length()) j=vec[j-1], count++, rs.push_back(i-A.length());
        }
        else{
            if (j>0) j=vec[j-1];
            if (j==0) i++;
        }
    }
    fout << count << "\n";
    for (auto c:rs) fout << c << " ";
    
    fin.close();
    fout.close();
}