Amit and Kisses
All submissions for this problem are available.
Amit love kisses. His girlfriend asked him to complete a task. If he does, she will give him kisses. She gives a string S and a pattern P and asked him to find count of occurances of pattern P in the string S. She told him to consider the count if at least first half of the pattern P matches with substring of S of length equal to length of pattern or at least last half of the pattern matches with the substring of S of length equal to length of pattern. First half of pattern means substring of pattern of length (n/2) where n is the length of pattern starting from 0th index. Last half of pattern means substring of pattern of length (n/2) starting from (n/2)th index in case pattern length is even and (n/2+1)th index if pattern length is odd, up to the last index. Help Amit in finding the answer. Note: Both S and P will consist lowercase letters.
Constraints and Subtasks
Subtask 1: 10 point
Subtask 2: 90 point
Input: cddabcabdcd abcab Output: 3
There can be only 7 possible substrings of length 5 (i.e. length of pattern ) available in String S.
1. cddab - In this Substring, last half of Substring i.e. "ab" matches with pattern hence our count is 1.
2. ddabc - In this Substring ,first half is "dd" and last half is "bc" neither of them matches with pattern's respective first and last half which is "ab" and "ab" respectively.
3. dabca - Here also neither first nor last half matches with pattern.
4. abcab - Here both first and last half matches hence we will increase our count to 2.
5. bcabd - Neither first nor last half matches with pattern.
6. cabdc - Neither first nor last half matches with pattern.
7. abdcd - Here first half of the substring "ab" matches with the first half of the pattern i.e. "ab". hence, count will become 3.
|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, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions