제출 #397102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
397102		abdzag	Lottery (CEOI18_lot)	C++17	20 / 100	902 ms	4224 KiB

lot

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b); i--);
#define all(v) v.begin(),v.end()
#define trav(a,v) for(auto&a:v)
#define  sz(a) a.size()
using namespace std;
const long long inf = 1e15;
typedef long long ll;
typedef vector<ll> vi;
void computeLPSArray(vector<ll> pat, int M, vector<ll>& lps);

// Prints occurrences of txt[] in pat[]
ll KMPSearch(vector<ll> pat, vector<ll>txt)
{
    int M = pat.size();
    int N = txt.size();
    ll res = 0;
    // create lps[] that will hold the longest prefix suffix
    // values for pattern
    vector<ll> lps(M);

    // Preprocess the pattern (calculate lps[] array)
    computeLPSArray(pat, M, lps);

    int i = 0; // index for txt[]
    int j = 0; // index for pat[]
    while (i < N) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }

        if (j == M) {
            res++;
            j = lps[j - 1];
        }

        // mismatch after j matches
        else if (i < N && pat[j] != txt[i]) {
            // Do not match lps[0..lps[j-1]] characters,
            // they will match anyway
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }
    return res;
}

// Fills lps[] for given patttern pat[0..M-1]
void computeLPSArray(vector<ll> pat, int M, vector<ll>& lps)
{
    int len = 0;

    lps[0] = 0; // lps[0] is always 0

    // the loop calculates lps[i] for i = 1 to M-1
    int i = 1;
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        }
        else // (pat[i] != pat[len])
        {
            // This is tricky. Consider the example.
            // AAACAAAA and i = 7. The idea is similar
            // to search step.
            if (len != 0) {
                len = lps[len - 1];

                // Also, note that we do not increment
                // i here
            }
            else // if (len == 0)
            {
                lps[i] = 0;
                i++;
            }
        }
    }
}
int main() {
	cin.sync_with_stdio(false);
	ll n, l;
	cin >> n >> l;
	vector<ll> s(n);
	rep(i, 0, n)cin >> s[i];
	ll q;
	cin >> q;
	rep(Q, 0, q) {
		vector<ll> res(n - l + 1);
		ll k;
		cin >> k;
		rep(start, 0, n - l + 1) {
			vector<ll> cur;
			rep(i, start, start + l) {
				cur.push_back(s[i]);
			}
            res[start] =KMPSearch(cur,s)-1;
		}
		trav(a, res)cout << a << " ";
		cout << endl;
	}
	return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20