Submission #397102

#TimeUsernameProblemLanguageResultExecution timeMemory
397102abdzagLottery (CEOI18_lot)C++17
20 / 100
902 ms4224 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...