Cod sursa(job #2321819)

Utilizator butasebiButa Gabriel-Sebastian butasebi Data 16 ianuarie 2019 17:46:04
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>
using namespace std;
char s[2000005], p[2000005];
int n, m, i, j, l[2000005], v[1005], k;
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f.getline(p, sizeof(p));
    f.getline(s, sizeof(s));
    n = strlen(p);
    m = strlen(s);
    j = 0;
    for(i = 1; i <= n; i ++)
    {
        while(j > 0 && p[j] != p[i])j = l[j - 1];
        if(p[j] == p[i])j++;
        l[i] = j;
    }
    j = 0;
    for(i = 0; i <= m; i ++)
    {
        while(j > 0 && p[j] != s[i])j = l[j - 1];
        if(p[j] == s[i])j++;
        if(j == n)
        {
            j = l[n - 1];
            if(k <= 1000)v[++k] = i - n + 1;
        }
    }
    g << k << "\n";
    for(i = 1; i <= min(k, 1000); i ++)
        g << v[i] << " ";
    return 0;
}