Cod sursa(job #2321565)

Utilizator butasebiButa Gabriel-Sebastian butasebi Data 16 ianuarie 2019 11:42:25
Problema Potrivirea sirurilor Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
#define Nmax 2000005
using namespace std;
char pattern[Nmax], sir[Nmax];
int i, j, n, m, suf[Nmax], v[1005], k;
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f.getline(pattern, sizeof(pattern));
    f.getline(sir, sizeof(sir));
    i = 1;
    j = 0;
    n = strlen(pattern);
    m = strlen(sir);
    while(i < n)
    {
        while(j > 0 && pattern[i] != pattern[j])j = pattern[j - 1];
        if(pattern[i] == pattern[j])
        {
            suf[i] = j + 1;
            i++;
            j++;
        }
        else i ++;
    }
    i = 0;
    j = 0;
    while(i < m)
    {
        while(j > 0 && sir[i] != pattern[j])j = suf[j - 1];
        if(sir[i] == pattern[j])
        {
            i++;
            j++;
            if(j == n)v[++k] = i - n;
        }
        else i++;
    }
    g << k << "\n";
    for(i = 1; i <= k; i ++)
        g << v[i] << " ";
    return 0;
}