Link to problem Once upon a time there was a famous actress. As you may expect, she played mostly Antique Comedies most of all. All the people loved her. But she was not interested in the crowds. Her big hobby were beads of any kind. Many bead makers were working for her and they manufactured new necklaces and bracelets every day. One day she called her main Inspector of Bead Makers (IBM) and told him she wanted a very long and special necklace. The necklace should be made of glass beads of different sizes connected to each other but without any thread running through the beads, so that means the beads can be disconnected at any point. The actress chose the succession of beads she wants to have and the IBM promised to make the necklace. But then he realized a problem. The joint between two neighbouring beads is not… Read more →
EppsNet Archive: String Algorithms
Competitive Programming: SPOJ – String Problem
Link to problem Substring of some string A is defined as one or more (not necessary succeeding) elements of the string with maintaining the sequence. There are given two strings, string VOKI and string TOKI. Write the program that will calculate the length of any shortest substring of string VOKI such as it is not substring of string TOKI. Input In first line of input file there is string VOKI and in second one is string TOKI. The only characters that will occur are lowercase characters of English alphabet (‘a’- ‘z’). String lengths will be less or equal to 1000. Note: input data will be such so there will always be a solution. Output In the first line of file you should print the length of wanted substring. Sample input banana anbnaanbaan Sample output 5 (eg. banna) Sample input babab babba Sample output 3 (eg. aab) Solution below . .… Read more →
Competitive Programming: SPOJ – Palindromes
A palindrome is a word, phrase, number or other sequence of units that has the property of reading the same in either direction, e.g. ‘racecar’, ‘solos’. Task You are given a number k (2 <= k <= 30000) and a non-empty string S whose length does not exceed 30000 lowercase letters. We say two palindromes are different when they start from different positions. How many different palindromes of the length k does S contains? Input The first line contains K. The second line contains S. K does not exceed the length of S. Output The first and only line should consist of a single number – the number of palindromes found. Example Input: 5 ababab Output: 2 Time limit: 0.100s Link to problem Solution below . . . Read more →
Competitive Programming: SPOJ – Distinct Substrings
Given a string, we need to find the total number of its distinct substrings. Input T- number of test cases. T<=20; Each test case consists of one string, whose length is <= 1000 Output For each test case output one number saying the number of distinct substrings. Example Sample Input: 2 CCCCC ABABA Sample Output: 5 9 Explanation for the testcase with string ABABA: len=1 : A,B len=2 : AB,BA len=3 : ABA,BAB len=4 : ABAB,BABA len=5 : ABABA Thus, total number of distinct substrings is 9. Link to problem Solution below . . . Read more →
Competitive Programming: POJ 2185 – Milking Grid
Description Every morning when they are milked, the Farmer John’s cows form a rectangular grid that is R (1 <= R <= 10,000) rows by C (1 <= C <= 75) columns. As we all know, Farmer John is quite the expert on cow behavior, and is currently writing a book about feeding behavior in cows. He notices that if each cow is labeled with an uppercase letter indicating its breed, the two-dimensional pattern formed by his cows during milking sometimes seems to be made from smaller repeating rectangular patterns. Help FJ find the rectangular unit of smallest area that can be repetitively tiled to make up the entire milking grid. Note that the dimensions of the small rectangular unit do not necessarily need to divide evenly the dimensions of the entire milking grid, as indicated in the sample input below. Input Line 1: Two space-separated integers: R and C… Read more →
Competitive Programming: POJ 1961 – Period
Description For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as AK, that is A concatenated K times, for some string A. Of course, we also want to know the period K. Input The input consists of several test cases. Each test case consists of two lines. The first one contains N (2 <= N <= 1,000,000) – the size of the string S. The second line contains the string S. The input file ends with a line, having the number zero on it. Output For each test case, output “Test… Read more →
Competitive Programming: POJ 1159 – Palindrome
Description A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome. As an example, by inserting 2 characters, the string “Ab3bd” can be transformed into a palindrome (“dAb3bAd” or “Adb3bdA”). However, inserting fewer than 2 characters does not produce a palindrome. Input Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from ‘A’ to ‘Z’, lowercase letters from ‘a’ to ‘z’ and digits from ‘0’ to ‘9’. Uppercase and lowercase letters are to be considered distinct.… Read more →