Cod sursa(job #1513795)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 29 octombrie 2015 23:07:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <string.h>

#define NMax 5000100

using namespace std;

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

int strl, patl, Z[NMax], sol[5010], k, l, r, conclen;
char conc[NMax];

void preprocess()
{
    Z[0] = conclen;
    int l = 0, r = 0;
    for (int i = 1; i <= conclen; i++) {
        if (i > r) {
            r = l = i;
            while (conc[r] == conc[r-l])
                r++;
            
            Z[i] = r - l;
            r--;
            
        }
        else {
            if (Z[i-l] < r-i+1)
                Z[i] = Z[i-l];
            else {
                l = i;
                while (conc[r] == conc[r - l])
                    r++;
                
                Z[i] = r - l;
                r--;
            }
        }
    }
}

int main()
{
    
    f>>(conc);
    patl = strlen(conc);
    conc[strlen(conc)] = '?';
    f>>(conc+strlen(conc));
    conclen = strlen(conc);
    
    preprocess();
    
    for (int i = 0; i < conclen; i++) {
        if (i > patl && Z[i] == patl) {
            sol[0]++;
            if (sol[0] <= 1000)
                sol[sol[0]] = i - patl - 1;
        }
    }
    
    g<<sol[0]<<"\n";
    
    for (int i=1; i<=sol[0] && i<=1000; i++)
        g<<sol[i]<<" ";
    
    return 0;
}