This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |