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
Category: Data Structure
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
10298
#include <iostream> #include <cstring> #include <cstdio> #include <string> using namespace std; int lps[1000005]; void prefixArray(string s) { memset(lps,0,sizeof(lps)); int len=0;//length of prev longest prefix int i=1; lps[0]=0; int length = s.size(); while(i<length) { if(s[i]==s[len]) { len+=1; lps[i]=len; i+=1; } else { if(len!=0) { len = lps[len-1]; } else { lps[i]=0; i+=1; } } } }
615
The problem is to finding a tree from a given graph.The main challenge is that the value of the node is not provided. So adjacency matrix can not be used to solve the problem. To define a tree for a directed graph : total edges = total vertices -1;root can not be more than one,
11610
To solve the problem indexes of the array are also needed to be updated and queried. #include <cstdio> #include <vector> #include <cstring> #include <algorithm> #include <iostream> using namespace std; struct RevPrime{ int reversePrime; int factorCount; }; int prime[1000001]; RevPrime arr[80000]; int Bit[2][80000]; vector<int> vb; int k=1; int reverse(int a) { int num=0; while(a) { num*=10;
10666
#include <iostream> #include <cstdio> using namespace std; //no of 1' indicate how many times at least it lost a game //no of 0' indicate how many times at least it lost a game //so if a team id does not contain a 0 it can be the last of the tournament at it pessimist decision
1428
The problem can be solved using Binary Indexed tree or Fenwick tree. #include <cstdio> #include <queue> #include <vector> #include <cstdlib> #include <cstring> #include <iostream> #include <string> #define SZ 100000+5 #define ll long long using namespace std; int arr[SZ]; ll Left[SZ],Right[SZ],sum[SZ]; int mx; ll Cumulative(int idx) { ll value=0; while(idx>0) { value += sum[idx]; idx -=
11402
#include <iostream> #include <cstdio> #include <cstring> #include <string> #define sz 1024001 #define INV 1 #define SET 2 #define RESET 3 using namespace std; struct segment{ int pending_op_typ; int sum; int left,right; int len; }; segment tree[sz*4]; string ss; void init(int node,int b,int e) { tree[node].len = e-b+1; tree[node].left=b; tree[node].right=e; tree[node].pending_op_typ=0; if(b==e) { if(ss[b]=='1') tree[node].sum=1; else
12436
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <vector> #define ll long long #define sz 250005 using namespace std; struct segment{ ll left,right; ll len; ll first_inc,last_inc; ll totalAB; bool isSetvalue; ll cary; ll sum; }; segment arr[sz*4]; void changeAB(ll frist_incr,ll last_incr,int node,ll step) { arr[node].totalAB += step; arr[node].first_inc += frist_incr; arr[node].last_inc += last_incr;
1282
Theory: The idea for solving the problem is: for any fibonacci word F(n) = F(n-1)+F(n-2) = F(n-2)+F(n-3)+F(n-2), so word F(n-2) is both suffix and prefix of word F(n). After observing a little more we can find that F(n-2) will always be the prefix for all the rest of the fibonacci word.Now find the minimum F(n-3)