Cod sursa(job #2321898)

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