Cod sursa(job #2909657)

Utilizator test9265test9265 test9265 Data 14 iunie 2022 15:38:35
Problema Potrivirea sirurilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 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=0, i, j;
    vector <int> vec(A.length(), 0);
    vector <int> rs;
    
    for (i=0, j=1; j<A.length();)
    {
        if (A[i]==A[j]) i++,j++;
        else{
            if (j>0) j=vec[j-1];
        }
        vec[j]=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();
}