The solution solves the problem within time limit but there are better solutions, by sorting the array using counting sort might give a better timing. There is also a solution without using a suffix array , simply by adding the string with itself and comparing which one is the lowest sub string. #include <iostream> #include
Month: January 2016
11512
#include <iostream> #include <cstdio> #include <sstream> #include <string> #include <algorithm> #include <cstring> using namespace std; string str; struct node{ int fst; int ed; int idx; }arr[1010]; int L[17][1010]; int RANK[1010]; int lcp[1010]; int FoundAtIndex; int cnt; string resStr; bool cmp(node a,node b) { return (a.fst==b.fst?(a.ed<b.ed?1:0):(a.fst<b.fst?1:0)); } void suffixArray() { for(int i=0;i<str.size();i++) L[0][i]=str[i]-'A'; int stp=1; for(int
11022
This is a dp problem where kmp algorithm(specially prefix function) is used to solve the problem. If a string is multiple of a repeated string then the difference between the string length and last index of the prefix table indicates the minimal length of the repeated string. A brief and nice discussion is available here . #include