Cod sursa(job #2737601)

Utilizator QwertyDvorakQwerty Dvorak QwertyDvorak Data 4 aprilie 2021 21:38:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
#include <bits/stdc++.h>
using namespace std;
/**
 /$$$$$$$$                 /$$                               /$$   /$$     /$$
|_____ $$                 | $$                              |__/  | $$    | $$
     /$$/         /$$$$$$ | $$  /$$$$$$   /$$$$$$   /$$$$$$  /$$ /$$$$$$  | $$$$$$$  /$$$$$$/$$$$
    /$$/         |____  $$| $$ /$$__  $$ /$$__  $$ /$$__  $$| $$|_  $$_/  | $$__  $$| $$_  $$_  $$
   /$$/           /$$$$$$$| $$| $$  \ $$| $$  \ $$| $$  \__/| $$  | $$    | $$  \ $$| $$ \ $$ \ $$
  /$$/           /$$__  $$| $$| $$  | $$| $$  | $$| $$      | $$  | $$ /$$| $$  | $$| $$ | $$ | $$
 /$$$$$$$$      |  $$$$$$$| $$|  $$$$$$$|  $$$$$$/| $$      | $$  |  $$$$/| $$  | $$| $$ | $$ | $$
|________/       \_______/|__/ \____  $$ \______/ |__/      |__/   \___/  |__/  |__/|__/ |__/ |__/
                               /$$  \ $$
                              |  $$$$$$/
                               \______/
*/
const string FILENAME = "strmatch";

ifstream fin(FILENAME + ".in");
ofstream fout(FILENAME + ".out");

string pat, txt, a;
unsigned int n, ansnr;
int main()
{
    int st, dr;
    st = dr = 0;
    fin >> pat;
    fin >> txt;
    a = pat + "$" + txt;
    n = a.length();
    int *z = new int[n];
    z[0] = -1;
    for(unsigned int i = 1; i < n; ++i)
    {
        if(i > dr)
        {
            st = dr = i;
            while(dr < n && a[dr] == a[dr - st])
                dr++;
            z[i] = dr - st;
            dr--;
        }
        else
        {
            int poz = i - st;
            if(z[poz] < dr - i + 1)
                z[i] = z[poz];
            else
            {
                st = i;
                while(dr < n && a[dr] == a[dr - st])
                    dr++;
                z[i] = dr - st;
                dr--;
            }
        }
    }
    for(int i = 0; i < n; ++i)
        if(z[i] == pat.length())
            ansnr++;
    fout << ansnr << "\n";
    for(int i = 0; i < n; ++i)
        if(z[i] == pat.length())
            fout << i - pat.length() - 1 << " ";
    fin.close();
    fout.close();
	return 0;
}