Cod sursa(job #2506448)

Utilizator MarcGrecMarc Grec MarcGrec Data 8 decembrie 2019 10:32:14
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#define DIM 2000000

#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

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

char A[DIM + 1], B[DIM + 1], la, lb;
int supra, indici[1001];

void Init();

int main()
{
    fin >> A >> B;

    la = strlen(A);
    lb = strlen(B);

    Init();

    int indice = 0, rasp = 0;
    bool ok = true;
    for (int i = 0; i < lb; ++i)
    {
        if (A[indice] == B[i])
        {
            if (i + supra < lb)
            {
                ok = A[indice] == B[i + supra];
            }
            else { ok = false; }

            if (indice == (la - 1))
            {
                ++rasp;
                if (rasp < 1001)
                {
                    indici[rasp] = i - la + 1;
                }

                if (ok)
                {
                    ++rasp;

                    if (rasp < 1001)
                    {
                        indici[rasp] = i - la + supra + 1;
                    }
                }

                ok = true;
                indice = 0;
            }
            else
            { ++indice; }
        }
        else
        {
            ok = true;
            indice = 0;
        }
    }

    fout << rasp << '\n';

    sort(indici + 1, indici + min(rasp, 1000));
    for (int i = 1; i <= rasp; ++i)
    {
        if (i > 1000)
        {
            break;
        }

        fout << indici[i] << ' ';
    }

    fin.close();
    fout.close();
    return 0;
}

void Init()
{
    for (int i = la - 2; i >= 0; --i)
    {
        if ((A[i] == A[la - 1]) && (A[la - i - 1] == A[0]))
        {
            bool ok = true;
            for (int j = la - i, k = 1; j < (la - 1); ++j, ++k)
            {
                if (A[j] != A[k]) { ok = false; break; }
            }

            if (ok)
            {
                supra = la - i - 1;
                break;
            }
        }
    }
}