Cod sursa(job #2800701)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 13 noiembrie 2021 18:58:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string a, b;
vector <int> v;

int lps[2000005];

int main()
{
    fin >> a >> b;
    a = " " + a;
    b = " " + b;

    lps[1] = 0;
    for (int i = 2; i < a.size(); i++)
    {
        char currLetter = a[i];
        int currIndex = lps[i - 1];
        
        while (currLetter != a[currIndex + 1] && currIndex != 0)
        {
            currIndex = lps[currIndex];
        }

        int result = currIndex;
        if (currLetter == a[currIndex + 1])
        {
            result++;
        }

        lps[i] = result;
    }

    int currIndex = 0;
    for (int i = 1; i < b.size(); i++)
    {
        char currLetter = b[i];

        while (currLetter != a[currIndex + 1] && currIndex != 0)
        {
            currIndex = lps[currIndex];
        }

        //currIndex is the length of the pattern
        if (currLetter == a[currIndex + 1])
        {
            currIndex++;
        }

        if (currIndex == a.size() - 1)
        {
            v.push_back(i - a.size() + 1);
        }

    }
    //     ABA
    //     CABBCABABAB
    //0 1 2 0 0 1 2 3 2 3 2
    fout << v.size() << '\n';
    for (int i : v)
    {
        fout << i << ' ';
    }
    fout << '\n';
    //ABACDABAB
    //00100123
}