Cod sursa(job #2909456)

Utilizator test9265test9265 test9265 Data 13 iunie 2022 19:31:12
Problema Potrivirea sirurilor Scor 0
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++;
        }
    }
    vec[0]=0;
    for (i=0, j=0;i<B.length();)
    {
        if (B[i]==A[j])
        {
            i++;
            j++;
        }
        if (j==A.length()) count++, rs.push_back(i-j), j=vec[j-1];
        if (B[i]!=A[j]) {
            if (j!=0) j=vec[j-1];
            else i++;
        }
    }
    fout << count << "\n";
    for (auto c:rs) fout << c << " ";
    
    fin.close();
    fout.close();
}