#include <iostream> #include <cstdio> #include <cstring> using namespace std; int arr[50005]; int binSearch(int num,int lw,int hi) { int mid; while(lw<hi) { mid = (hi+lw)/2; if(num<arr[mid]) hi = mid; else if(num>=arr[mid]) lw = mid+1; } return hi; } int main() { int N,Q,a; int len,qry,idx; while(scanf("%d",&N)!=EOF) { scanf("%d",&arr[0]); len = 1; for(int i=1;i<N;i++) { scanf("%d",&a); if(a!=arr[len-1])
Year: 2016
719
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
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