Cod sursa(job #1588344)

Utilizator radarobertRada Robert Gabriel radarobert Data 2 februarie 2016 23:14:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <iostream>

using namespace std;

string text, pattern;
int prefix[2000002];
int sol[1002];

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

    in >> pattern;
    in >> text;

    for (int i = 1; i <= pattern.size(); i++)
        if (pattern[i] == pattern[prefix[i-1]])
            prefix[i] = prefix[i-1] + 1;
        else
            prefix[i] = (pattern[i] == pattern[0]);
    int nr_sol = 0;
    for (int i = 0, j = 0; i <= (int)text.size() - (int)pattern.size();)
    {
        for (; j < (int)pattern.size(); j++)
            if (text[i+j] != pattern[j])
                break;
        if (j == (int)pattern.size() &&  nr_sol <= 1000)
        {
            ++nr_sol;
            if (nr_sol <= 1000)
                sol[nr_sol] = i;
        }
        if (j > 0)
            j--;
        i += (j + 1 - prefix[j]);
        j = prefix[j];
    }

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

    return 0;
}