Sub String Manipulation
All submissions for this problem are available.
Ram was given a puzzle by his brother. Ram's brother has two sets of cards. One consist of the string S and another consist of the string P, where P and S are lowercase English characters. P is the substring of S. Ram's brother has set of Q queries that are needed to be performed on the strings P and S. The query is of the form N and C where N is a positive integer and C is a lowercase character.
For every query Qi, Ram's work is to change the index value N (Assume 0 based indexing) of the string S to the character C.
The Query will be executed in the order. Ram's work is to find the minimum number of queries that are executed sequentially from the start so that the string P no longer exist as a substring in S.
If the String P exist in S even after executing all the Q queries then return the answer as -1.
Help ram to solve the puzzle.
First line contains a single integer T denoting the number of test cases.
First line of each test case contains a single string S.
Second line of each test case contains a single string P
Third line of each test case contains a single integer Q defining the number queries.
The next Q lines of the test case contains N and C which are space seperated.
1 ≤ T ≤ 50.
1 ≤ |S| ≤ 2.105.
1 ≤ |P| ≤ |S|.
1 ≤ Q ≤ |S|.
0 ≤ N ≤ |S|.
For each testcase T, return a single integer denoting the minimum number of queries after which the string P ceases to exist in string S.
Test Case 1
Here S is a[bc]de.
Here P is bc.
After the 1st query the S is p[bc]de.
After the 2nd query the S is p[qc]de, now the string P is not in string S, so after the 2nd query S is changed so the answer is 2.
Test Case 2
Here S is ab[cde].
Here P is cde.
After the 1st query the S is tb[cde].
After the 2nd query the S is tz[cde].
Even, after all the updates the string P is in the string S, so the answer is -1.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions