Cod sursa(job #1964159)

Utilizator andrei232000Andrei Maria andrei232000 Data 13 aprilie 2017 10:33:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 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, j, p[2000003], l, L, contor, start[2000003];
int main()
{
    fin>>c;
    fin>>sir;
    l = strlen(c);
    L = strlen(sir);
    for(i = 1; i < l; ++i)
    {
        while(j)
        {
            if(c[i] == c[j])
            {
                ++j;
                p[i] = j;
                break;
            }
            j = p[j - 1];
        }
        if(!j)
        {
            if(c[i] == c[j])
            {
                ++j;
                p[i] = j;
            }
        }
    }
    j = 0;
    for(i = 0; i < L; ++i)
    {
        while(j)
        {
            if(c[j] == sir[i])
            {
                ++j;
                break;
            }
            j = p[j - 1];
        }
        if(!j)
        {
            if(c[j] == sir[i])
            {
                ++j;
            }
        }
        else if(j == l)
        {
            start[contor] = i - l + 1;
            ++contor;
            j = p[l - 1];
        }
    }
    fout<<contor<<'\n';
    for(i = 0; i < contor; ++i)
    {
        fout<<start[i]<<" ";
    }
    return 0;
}