[go: up one dir, main page]
Scribd
Upload
31 views2 pages

Dsa Bootcamp Practice Questions PDF

Uploaded by

Saurabh Bhandari
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
31 views2 pages

Dsa Bootcamp Practice Questions PDF

Uploaded by

Saurabh Bhandari
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

DSA BOOTCAMP PRACTICE QUESTIONS

 KMP ALGORITHM (Code)-


#include <bits/stdc++.h>
using namespace std;
void computeLPSArray(string pat, int M, vector<int>& lps);

// Prints occurrences of pat[] in txt[]


void KMPSearch(string pat, string txt)
{
int M = pat.size();
int N = txt.size();
vector<int> lps(M);
computeLPSArray(pat, M, lps);

int i = 0; // index for txt[]


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

if (j == M) {
printf("Found pattern at index %d ", i - j);
j = lps[j - 1];
}
else if (i < N && pat[j] != txt[i])
{
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
}
void computeLPSArray(string pat, int M, vector<int>& lps)
{
// length of the previous longest prefix suffix
int len = 0;
lps[0] = 0; // lps[0] is always 0
int i = 1;
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if (len != 0)
{
len = lps[len - 1];
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
}
int main()
{
string txt = "ABABDABACDABABCABAB";
string pat = "ABABCABAB";
KMPSearch(pat, txt);
return 0;
}

 Leetcode Questions

S.No. Problem Problem Name Link


Number
1. 686 Repeated String https://leetcode.com/problems/repeated-
Match
string-match/description/
2. 459 Repeated Substring https://leetcode.com/problems/repeated-
Pattern
substring-pattern/description/
3. 214 Shortest Palindrome https://leetcode.com/problems/shortest-
palindrome/description/
4. 1392 Longest Happy Prefix https://leetcode.com/problems/longest-
happy-prefix/description/

NOTE: Practice these question for more clarity, All the best.

You might also like