Cod sursa(job #1963092)

Utilizator andrei232000Andrei Maria andrei232000 Data 12 aprilie 2017 11:54:42
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char c[2000003], sir[2000003];
int i, k, contor, p[2000003], l, L, start[2000003];
int main()
{
    fin>>c;
    fin>>sir;
    l = strlen(c);
    L = strlen(sir);
    k = 0;
    if(l <= L)
    {

        for(i = 1; i < l; ++i)
        {
            if(c[k] == c[i])
            {
                ++k;
                p[i] = k;
            }
            else
            {
                k = 0;
            }
        }
        for(i = 0; i < L; ++i)
        {
            if(c[k] == sir[i])
            {
                ++k;
                if(k == l)
                {
                    k = p[l - 1];
                    start[contor] = i - l + 1;
                    ++contor;
                }
            }
            else
            {
                if(k)
                {
                    k = p[k - 1];
                    if(k)
                    {
                        --i;
                    }
                }
            }
        }
    }
    fout<<contor<<endl;
    for(i = 0; i < contor; ++i)
    {
        fout<<start[i]<<endl;
    }
    return 0;
}