Cod sursa(job #2351790)

Utilizator BurlacuMateiBurlacu Matei BurlacuMatei Data 22 februarie 2019 18:13:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <cstring>
#define MAX 2000010

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


char a[MAX], b[MAX];
int lg, lgb, d[MAX], db[MAX];
int c, pozc[MAX];

int main()
{int k, i;

    fin >> (a + 1);
    fin >> (b + 1);

    lg = strlen(a + 1);
    lgb = strlen(b + 1);
    for(i = 2, k = 0;i<=lg;i++)
    {
        if(a[i] == a[k + 1])
        {
            k++;
            d[i] = k;
        }
        else
            {
                while(a[k + 1] != a[i] && k)
                k = d[k];

                if(a[k + 1] == a[i])
                    d[i] = k + 1;
                else d[i] = 0;
            }

    }

    for(i=1, k=0;i<=lgb;i++)
    {
        if(b[i] == a[k + 1])
        {
            k++;
            db[i] = k;
        }
        else
            {
                while(a[k + 1] != b[i] && k)
                k = d[k];

                if(a[k + 1] == b[i])
                    {db[i] = k + 1; k++;}
                else db[i] = 0;
            }

        if(db[i] == lg){
            c++;
            pozc[c] = i - lg;
        }
    }


    fout << c << '\n';
    for(i=1;i<=c;i++)
        fout << pozc[i] << ' ';
    return 0;
}