Cod sursa(job #1409603)

Utilizator radarobertRada Robert Gabriel radarobert Data 30 martie 2015 16:52:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <cstring>

using namespace std;

char a[2000002], b[2000002];
int p[2000002];
int pos[1002];

int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");

    in >> a;
    in >> b;
    int n = strlen(a);
    int m = strlen(b);

    int k = 0;
    for (int i = 1; i < n; i++)
    {
        if (a[i] == a[k])
            k++;
        else
            k = (a[i] == a[0]);
        p[i] = k;
    }

    int j = 0;
    int sol = 0;
    for (int i = 0; i <= m - n;)
    {
        for (; j < n; j++)
            if (b[i+j] != a[j])
                break;
        if (j == n)
        {
            ++sol;
            if (sol <= 1000)
                pos[sol] = i;
        }
        j--;
        if (j < 0)
            j = 0;
        i += (j+1 - p[j]);
        j = p[j];
    }

    out << sol << '\n';
    for (int i = 1; i <= sol && i <= 1000; i++)
        out << pos[i] << ' ';
    out << '\n';

    return 0;
}