Cod sursa(job #2725303)

Utilizator BalogOctavianBalog Octavian Gheorghe BalogOctavian Data 18 martie 2021 19:23:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <fstream>
#include <sstream>
#include <vector>
#define maxRange 2000001

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int n,np, pi[maxRange], z[maxRange];
string a,b;
vector <int> v;
void zalgorithm()
{
    int left = 0, right = 0;
    for(int k = 1; k < n; k++)
    {
        if(k>right)
        {
            left = right = k;
            while (right < n && b[right] == b[right - left])
            {
                right++;
            }
            z[k] = right - left;
            right --;
        }
        else
        {
            int k1 = k - left;
            if(z[k1] < right - k + 1)
            {
                z[k] = z[k1];
            }
            else
            {
                left = k;
                while (right < n && b[right] == b[right - left])
                {
                    right++;
                }
                z[k] = right - left;
                right --;
            }
        }
    }
}
/*
void prefix()
{
    int k = 0;
    pi[1] = 0;
    for(int i = 2; i <= n; i++)
    {
        while(k && v[k+1] != v[i]) k = pi[k];
        if(v[k+1] == v[i]) k++;
        pi[i] = k;
    }
}
*/
int main()
{
    b = "";

    f >> a;

    np = a.length();
    b += a + '$';
    a = "";
    f >> a;

    b += a;

    n = b.length();

    zalgorithm();

    for(int i = np+1; i < n; i++)
    {
        if (z[i] == np) v.push_back(i - (np + 1));
    }
    g << v.size() << '\n';
    for(int i = 0; i < v.size() && i < 1000; i++)
    {
        g << v[i] << ' ';
    }
    return 0;

}