OJ Board

Posted: **Sun Aug 15, 2004 8:52 pm**

Problem: given a text determine lexicographically maxiaml suffix of a string in O(n).

For example:
cacbca has the max suffix cbca.

I read that this can be done with technique similar to one used in KMP, using the maximal suffix and at the same time a prefix of a word, but I don't know how to implement it.

Any help is appreciated

Posted: **Mon Aug 16, 2004 2:46 am**

build a suffix tree then start at the root and always go down to the lexicographically highest child until you hit a leaf. this will end you with the suffix you are looking for.

One way to build a suffix tree is Ukkonen's Algorithm. This site explains
how that works and even has a sample implementation in C++ at the
very end.

http://www.dogma.net/markn/articles/suffixt/suffixt.htm

Posted: **Mon Aug 16, 2004 8:18 pm**

There are simpler algorithms wich are specialised for this task. Like the next one (it gets thwe minimal suffix not the maximal one):

Code: Select all

for (i = 0; i<N;i++) C[N+i]=C[i];
   k=0;n=1;l=0;
   while (n<N&&k+l+1<N) {
	   if (C[k+l]==C[n+l]) l++;
	   else if (C[k+l] < C[n+l]) {
             n=n+l+1;l=0;
	   } else {
		   h=n>k+l+1?n:k+l+1;
		   k=h;n=1+h;l=0;
	   }
   }

OJ Board

Maximal suffix

Maximal suffix