InfiniteString
SRM 658 · 2015-05-01 · by cgy4ever
SRM 658 · 2015-05-01 · by cgy4ever · Brute Force
Problem Statement
Problem Statement
Given a string s, let f(s) denote the infinite string obtained by concatenating infinitely many copies of s.
For example, if s = "abc" then f(s) = "abcabcabcabc...".
Note that the string f(s) still has a beginning. Hence, f("abc") and f("bca") are two different infinite strings: the first one starts with an 'a' while the other starts with a 'b'.
Sometimes, two different finite strings can produce the same infinite string. For example, f("abc") is the same as f("abcabc").
You are givenString s s and t.
Check whether f(s) equals f(t).
If the two infinite strings are equal, return "Equal".
Otherwise, return "Not equal".
Note that the string f(s) still has a beginning. Hence, f("abc") and f("bca") are two different infinite strings: the first one starts with an 'a' while the other starts with a 'b'.
Sometimes, two different finite strings can produce the same infinite string. For example, f("abc") is the same as f("abcabc").
You are given
Constraints
- s will contain between 1 and 50 elements, inclusive.
- t will contain between 1 and 50 elements, inclusive.
- Each character in s will be a lowercase English letter ('a'-'z').
- Each character in t will be a lowercase English letter ('a'-'z').
Examples
0)
"ab" "abab" Returns: "Equal"
Both string will generate "ababababab...".
1)
"abc" "bca" Returns: "Not equal"
2)
"abab" "aba" Returns: "Not equal"
The first one will generate "abababab...", but the second one will generate "abaaba...".
3)
"aaaaa" "aaaaaa" Returns: "Equal"
4)
"ababab" "abab" Returns: "Equal"
Submissions are judged against all 79 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class InfiniteString with a public method string equal(string s, string t) · 79 test cases · 2 s / 256 MB per case