/* SHORTEST STRING PERIOD (already sumbitted as an assignment) Write a program to find the shortest period of a string. A period of a string S is a number p such that if we split the string into parts of length p, all these parts will be equal. For example, the string ababab has period 2, because after the splitting we get ab ab ab (three equal parts). Formally, for each reasonable i it is true that S[i]=S[i+p] The shortest period is the smallest such number. For example: Input: abababab Output: 2 4 is also a period of this string, but we are looking for the smallest Input: ababcababc Output: 5 Input: tomatoes Output: 8 this string doesn't have any period, so we can say that its period is its length Hard task: Solve this challenge in linear time in relation to the length of the string (O(n)). https://www.sololearn.com/post/37247/?ref=app Not sure if the solution is truly O(n). Finding true Time Complexity has always been an issue. Sometimes I get it right and sometimes not :) */ #include #include #include using namespace std; // Tries to find the minimum string period // of a string by trying out substrings of // length 1 to half of string size size_t min_period(string_view to_search, string_view search_in) { // string to search is already a substr // so start the count with 1 size_t substr_count{1}; // the position to search needs to be // equal to the length of the substring // to find onwards size_t pos{to_search.size()}; while((pos = search_in.find(to_search,pos)) != string::npos) { substr_count++; pos += to_search.size(); } // substring count times string period // must match input string length else // string period is not proper string // period, in that case return 0 if(substr_count*to_search.size() != search_in.size()) { return 0; } // you have found the string period return to_search.size(); } void str_period(string_view instr) { size_t period{0}; for(size_t x{0}; x

[Challenge] Minimum_String_Period.cpp