Cod sursa(job #2909460)

Utilizator test9265test9265 test9265 Data 13 iunie 2022 19:40:24
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 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()+1, 0);
    vector <int> rs;
    
    j = 0;
    i = 1;
    while (i < A.length()) {
        if (A[i] == A[j]) {
            j++;
            vec[i] = j;
            i++;
        }
        else // (pat[i] != pat[len])
        {
            // This is tricky. Consider the example.
            // AAACAAAA and i = 7. The idea is similar
            // to search step.
            if (j != 0) {
                j = vec[j - 1];
  
                // Also, note that we do not increment
                // i here
            }
            else // if (len == 0)
            {
                vec[i] = 0;
                i++;
            }
        }
    }
    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];
        else 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();
}