Cod sursa(job #1939995)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 26 martie 2017 11:55:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <cstring>

using namespace std;

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

int n,m,i,l,p[2000005],sol,v[1005];
char a[2000005],q,b[2000005];

int main()
{
    fin >> a;
    n = strlen (a);
    for (i=n; i>=1; i--)
        a[i] = a[i-1];
    a[n+1] = 0;
    fin >> b;
    m = strlen (b);
    for (i=m; i>=1; i--)
        b[i] = b[i-1];
    b[m+1] = 0;
    l = 0;
    p[0] = 0;
    for (i=2; i<=n; i++)
    {
        while (l != 0 && a[i] != a[l+1])
            l = p[l];
        if (a[i] == a[l+1])
            l++;
        p[i] = l;
    }
    l = 0;
    for (i=1; i<=m; i++)
    {
        while (l != 0 && b[i] != a[l+1])
            l = p[l];
        if (b[i] == a[l+1])
            l++;
        if (l == n)
        {
            sol++;
            if (sol <= 1000)
                v[sol] = i-n;
            l = p[l];
        }
    }
    fout << sol << "\n";
    if (sol >= 1000)
        sol = 1000;
    for (i=1; i<=sol; i++)
        fout << v[i] << " ";
    return 0;
}