Блог пользователя terminated

Автор terminated, 12 лет назад, По-английски

I recently was doing this problem on spoj.It was about finding the number of distinct sub-string in a string.Suffix array was to be used but i didn't knew about suffix arrays.I searched on net and learned about suffix array but when I moved towards implemention all codes available online were a bit lengthy so I implemented my own and came out with this--

#include "bits/stdc++.h"
using namespace std;
 int main(int argc, char const *argsorted_suffixes[])
{
	
		set<string> set1;

		string s="aabaab";

		int n=s.length();
		/*inserting all possible suffixes of string in set1*/
		for (int i = 0; i < n ; ++i) 
		{
			set1.insert(s.substr(i,n-i));
		}

		vector<string> sorted_suffixes(set1.begin(),set1.end()); /*suffix vector(array)*/
		/*Building LCP table*/
		int LCP[set1.size()];

		LCP[0]=0;

		string s4,s5;

		for(int i=1;i<sorted_suffixes.size();i++)
		{
			s4=sorted_suffixes[i-1];
			s5=sorted_suffixes[i];
			int c=0;
			for(int j=0;j<s4.length();j++)
			{
				if(s4[j]==s5[j])
					c++;
				else
					break;
			}
			LCP[i]=c;


		}
		/*LCP TABLE CONSTRUCTED*/
		for (int i = 0; i < sorted_suffixes.size(); ++i)
		{
			cout<<sorted_suffixes[i]<<" "<<LCP[i]<<endl;
		}
}

Here I have not constructed a suffix array rather I have a vector of strings which has the suffixes in sorted order and I think it doesn't make a difference to either have a container of indexes or to have a container of sorted suffixes. This is easy to code and understand.I have tested it for many cases and it works fine, If there is any bug in my code please point out!

  • Проголосовать: нравится
  • -21
  • Проголосовать: не нравится

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Each insertion to a set takes O(logN) comparisons. Here each comparison is between 2 strings and hence will take O(length) time. So, the complexity of building the set is O(n * (length) * logn) which is O(n^2logn). This will time out in most of the problems.

»
12 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

set1.insert(s.substr(i,n-i));

Is this correct??? i guess it must be : set1.insert(s.substr(i,n));

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Well, here are some not so lengthy implementation. Kasai() computes lcp array.

: #67rZRE

: #4AsFVi