Участник:Kozub/Ada and Terramorphing

Материал из DISCOPAL
Перейти к: навигация, поиск

Ссылка на задачу на spojcode: https://www.spoj.com/problems/ADAPHOTO/

Использовался С++14(gcc 8.3)

 
#include <iostream>
#include <cstring>
#include <algorithm> 
 
using namespace std;
 
bool cmp(char * a, char * b) 
{ 	
	return strcmp(a, b) < 0;
} 
 
int main(){
	const long int max_l = 1000005;
 
	char X[2*max_l];
 
	//Build concat row with special end symbols
	unsigned int lX, lY, i;
 
	cin>>X;
	lX = strlen(X);
	*(X+lX) = '$';
	cin>>X+lX+1;
 
	unsigned int n = strlen(X)+1;
	*(X+n-1) = '#';
	*(X+n)='\0';
 
	//Make suffix array
	char ** suff_arr = new char*[n];
	for(int i =0;i<n;i++)
		suff_arr[i] = X+i;
 
 
	sort(suff_arr, suff_arr + n, cmp);
 
 
	//Calculating longest commont prefix
	unsigned int * rank  = new unsigned int[n];
	unsigned int * LCP = new unsigned int[n];
 
	for(int i = 0;i<n;i++)
		rank[suff_arr[i]-X] = i;
 
    unsigned int h = 0;
    unsigned int k;
    for(int i=0;i<n;i++){
		if (rank[i] > 0){
			k = suff_arr[rank[i]-1] - X;
			while(X[i+h] == X[k+h]){
				++h;}
		}
 
		LCP[rank[i]] = h;
		if (h>0)
			h--;
	}  
 
	 //Find longest common substring
	 unsigned int mx = 0;
	for(int i=1; i<n;i++){
 
		if ((suff_arr[i] - X>=lX+1) != (suff_arr[i-1] - X>=lX+1) && mx < LCP[i])
			mx= LCP[i];
	}
 
	cout<<mx<<endl;
 
    return 0;
}