Cod sursa(job #1399409)

Utilizator radarobertRada Robert Gabriel radarobert Data 24 martie 2015 18:51:06
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

const int MAXL = 2000002;

char a[MAXL], b[MAXL];
int p[MAXL];
int sol[1002];

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

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

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

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

    out << nr_sol << '\n';
    for (int i = 1; i <= nr_sol && i <= 1000; i++)
        out << sol[i] << ' ';
    if (nr_sol > 0)
        out << '\n';

    return 0;
}