Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Facer’s string
Description Minifacer was very happy these days because he has learned the algorithm of KMP recently. Yet his elder brother, Hugefacer, thought that Minifacer needs a deeper understanding of this algorithm. Thus Hugefacer decided to play a game with his little brother to enhance his skills. First, Hugefacer wrote down two strings . Then Minifacer tried to find a substring S2 of S3 which meets the following requirements: 1) S1 should have a length of S3k (which is a constant value); 2) should also be the substring of S3. After several rounds, Hugefacer found that this game was too easy for his clever little brother, so he added another requirement: 3) the extended string of S2 should NOT be the substring of S3. Here the extended string of S2 is defined as S3 plus its succeed character in S3 (if S1 does not have a succeed character in S3, the extended string of S1 is S3 + ' ' which will never appear in S3). For example, let S2 be "ababc", if we select the substring from the first character to the second character as S1 (so S3 equals "ab"), its extended string should be "aba"; if we select the substring from the third character to the fourth character as S3, its extended string should be "abc"; if we select the substring from the fourth character to the fifth character as S3, its extended string should be "bc".S3Since the difficult level of the game has been greatly increased after the third requirement was added, Minifacer was not able to win the game and he thought that maybe none of the substring would meet all the requirements. In order to prove that Minifacer was wrong, Hugefacer would like to write a program to compute number of substrings that meet the three demands (Note that two strings with same appearance but different positions in original string S1 should be count twice). Since Hugefacer do not like characters, he will use non-negative integers (range from 0 to 10000) instead. Input There are multiple test cases. Each case contains three lines: the first line contains three integers m represents the length of and S2k represents the length of substring; the second line contains string and the third line contains string S1. Here 0 ≤ S2n, m ≤ 50000. Input ends with EOF.Output For each test case, output a number in a line stand for the total number of substrings that meet the three requirements. Sample Input 5 5 2 1 2 1 2 3 1 2 3 4 5 5 5 3 1 2 1 2 3 1 2 3 4 5 Sample Output 2 1 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator