Author: bikram947
Tester: pratims10
DIFFICULTY:
EASY.
PREREQUISITES:
String, Substring, KMP.
PROBLEM:
You are given a String S of length N consisting of only 0 and 1. There are K no of queries where each query consists of one character ′L′ or ′R′ and one integer P. Your task is to rotate the String in left (for input L) or in right (for input R) direction for P times and form a new string by taking the last character of the rotated String after the end of the rotation of each query. Now you should check whether the newly generated String from the queries is a substring of the given original String or not. If it is a substring you should print YES, else you should print NO.
EXPLANATION:
Actually you need not rotate the original string. You can fix an index pointer that will indicate the last character after each rotation.
Initialize index pointer as 0. For left rotation increment the index pointer by ‘P’ and if it is greater than the length of the string then subtract length ‘N’ from the index.
Similarly, for right rotation decrement the index pointer by ‘P’ and if it is less than ‘1’ then add the index to the length ‘N’.
The index pointer will point to the last character and add it to the newly generated string.
Finally, to check whether the newly generated string is a substring of the original string or not, use the KMP algorithm. You can learn the KMP algorithm from here.
SOLUTIONS:
Setter's Solution
def is_substring(pat, txt):
M = len(pat)
N = len(txt)
lps = [0]*M
j = 0
computeLPSArray(pat, M, lps)
i=0
while i < N:
if pat[j] == txt[i]:
i += 1
j += 1
if j == M:
return True
j = lps[j-1]
elif i < N and pat[j] != txt[i]:
if j != 0:
j = lps[j-1]
else:
i += 1
return False
def computeLPSArray(pat, M, lps):
len = 0
lps[0]
i = 1
while i < M:
if pat[i]== pat[len]:
len += 1
lps[i] = len
i += 1
else:
if len != 0:
len = lps[len-1]
else:
lps[i] = 0
i += 1
t=int(input())
for j in range(t):
n,k=map(int,input().strip().split(" "))
s=input()
index=0
sub_str=""
for i in range(k):
d=[x for x in input().split()]
if(d[0]=='L'):
index+=int(d[1])
if(index>n):
index-=n
else:
index-=int(d[1])
if(index<1):
index+=n
sub_str+=s[index-1]
if(is_substring(sub_str,s)):
print("YES")
else:
print("NO")
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll int
void computeLPSArray(string pat, int M, int lps[]);
bool KMPSearch(string pat,string txt)
{
int M = pat.length();
int N = txt.length();
int lps[M];
computeLPSArray(pat, M, lps);
int i = 0;
int j = 0;
while (i < N)
{
if (pat[j] == txt[i])
{
j++;
i++;
}
if (j == M)
{
return true;
j = lps[j - 1];
}
else if (i < N && pat[j] != txt[i])
{
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
return false;
}
void computeLPSArray(string pat, int M, int* lps)
{
int len = 0;
lps[0] = 0;
int i = 1;
while (i < M)
{
if (pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if (len != 0)
{
len = lps[len - 1];
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
}
int main()
{
ll i,j,k,m,n,t,q;
cin>>t;
while(t--)
{
cin>>n>>q;
string s;
cin>>s;
char ch;
string str;
ll pos=n-1;
while(q--)
{
ll x;
cin>>ch>>x;
if(ch=='L')
{
pos+=x;
pos%=n;
}
else
{
pos-=x;
if(pos<0)
pos+=n;
}
str+=s[pos];
}
if(KMPSearch(str,s))
cout<<"YES\n";
else cout<<"NO\n";
}
}