Cod sursa(job #2040227)

Utilizator TherevengerkingSurani Adrian Therevengerking Data 15 octombrie 2017 15:14:18
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int>ans;
#define pb push_back
const int Nmax = 2000000 + 5;
char N[Nmax + 5], H[Nmax + 5];
int n, h, s[Nmax], cnt;
int f = 0;
void afis()
{
    fout << cnt << '\n';
    for(auto i : ans)
        fout << i << " ";
}
int main()
{
    fin >> (N + 1) >> (H + 1);
    n = strlen(N + 1); h = strlen(H + 1);

    s[0] = -1;
    s[1] = 0;
    for(int i = 2; i <= n; ++i)
    {
        int k = i - 1;
        char c = N[i];
        while(s[k] != -1 && N[s[k] + 1] != c)
            k = s[k];
        s[i] = s[k] + 1;
    }

    f = 0;
    for(int i = 1; i <= h; ++i)
    {
        if(N[f + 1] == H[i])
        {
            f++;
            if(f == n)
            {
                cnt ++;
                if(cnt <= 1000)
                ans.pb(i - n);
                f = s[f];
            }
        }
        else
        {
            while(N[s[f] + 1] != H[i] && f != -1)
                f = s[f];
        }
        if(f == -1)f = 0;
    }
    afis();
    return 0;
}