Cod sursa(job #2224378)

Utilizator razviii237Uzum Razvan razviii237 Data 23 iulie 2018 21:04:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
//2
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int maxn = 2e6+5;

string p, t;
int prefix[maxn];
int rez[maxn], rezk;
int n, m;

void prefix_calculate()
{
    int a = 0, i = 0;
    prefix[1] = 0;
    for(i = 2; i <= n; i ++)
    {
        while(a > 0 && p[a+1] != p[i])
            a = prefix[a];
        if(p[a+1] == p[i])
            ++a;
        prefix[i] = a;
    }
}

void kmp_calculate()
{
    int i = 1, j = 1, k = 1;
    while(m - k + 1 >= n)
    {
        while(j <= n && t[i] == p[j]){
            i ++;
            j ++;
        }
        if(j > n)
            rez[++rezk] = k;
        if(prefix[j-1] > 0)
            k = i - prefix[j-1];
        else
        {
            if(i == k) i++;
            k = i;
        }
        if(j > 1)
            j = prefix[j-1] + 1;
    }
}

int main()
{
    f >> p;
    f >> t;

    p = " " + p;
    n = p.size() - 1;
    t = " " + t;
    m = t.size() - 1;

    prefix_calculate();
    kmp_calculate();

    g << rezk << '\n';
    int file_size = min(rezk, 1000);
    for(int i = 1; i <= file_size; i ++)
        g << rez[i]-1 << ' ';

    return 0;
}