Cod sursa(job #1913846)

Utilizator alexandru822Bosinta Alexandru alexandru822 Data 8 martie 2017 14:22:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <string.h>

using namespace std;

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

const int N_MAX = 2000000;
const int M_MAX = 2000000;
const int NumberOfPositions = 1000;

char s[1 + N_MAX + 1 + M_MAX];
int fail[1 + N_MAX + 1 + M_MAX], position[NumberOfPositions], nr;

void kmp()
{
    in >> 1 + s;
    int sizeA = strlen(1 + s);
    s[1 + sizeA] = '$';
    in >> 1 + s + sizeA + 1;
    fail[0] = -1;
    fail[1] = 0;
    for(int i = 2; s[i] != 0; i++)
    {
        int j = fail[i-1] + 1;
        while(j > 0 && s[i] != s[j])
            j = fail[j-1] + 1;

        if(j == 0) j = 1;
        if(s[i] == s[j])
            fail[i] = j;
        else fail[i] = 0;
        if(fail[i] == sizeA)
        {
            nr++;
            if(nr<1000)
                position[nr-1] = i - 2*sizeA - 1;
        }
    }
}

void write()
{
    out << nr << "\n";
    for(int i = 0; i < nr & i < 1000; i++)
        out << position[i] << " ";
}


int main()
{
    kmp();
    write();
    return 0;
}