首页 > 求最长公共子串
头像
上善若水~~
编辑于 2020-11-13 14:24
+ 关注

求最长公共子串

var longComSubstr = function (){
	// 短字符串
	this.smallStr='';
	// 长字符串
	this.largeStr='';
	// 短字符串长度
	this.smallLen=0;
	// // 排列标识
	// this.combinationIndex=0;
	// 最大子串数组
	this.longComSubstrArr=[];
	// // 中间处理用数组
	// this.midDealArr=[];
	// 去重的最大子串数组
	this.longComSubstrArrNew=[];
}

// 设置长字符串 短字符串
longComSubstr.prototype.setSmallLarge=function(str1,str2){
	if(!(str1.length <= 5000 && str1.length >= 1)){
		console.log('参数:'+str1+'不符合要求');
		return
	}
	if(!(str2.length <= 5000 && str2.length >= 1)){
		console.log('参数:'+str2+'不符合要求');
		return
	}
	if(str1.length > str2.length){
		this.smallStr = str2;
		this.largeStr = str1;
	}else{
		this.smallStr = str1;
		this.largeStr = str2;
	}
}

// 设置短字符串长度
longComSubstr.prototype.setSmallLen=function(){
	this.smallLen = this.smallStr.length;
}

// 核心逻辑处理函数,需要迭代,注意跳出迭代
longComSubstr.prototype.getSmallSonStr=function(ind){
	var that = this;
	// 短串长度为1时
	if(that.smallLen == 1){
		if(that.largeStr.indexOf(that.smallStr)>=0){
			that.longComSubstrArr.push(that.smallStr);
			return
		}else{
			return
		}
	}
	// // 短串长度大于等于2
	if(that.longComSubstrArr.length>0 && ind<=that.smallLen){
		console.log('已经找到最大字符串啦!');
		return
	}
	var midArr = [];
	if(ind == that.smallLen){
		if(that.largeStr.indexOf(that.smallStr)>=0){
			that.longComSubstrArr.push(that.smallStr);
		}
	}
	if(ind <= that.smallLen){
		for(var i = 0,j=ind;i<=j;i++){
			var midStr = that.smallStr.substr(i,that.smallLen-ind)
			if(that.largeStr.indexOf(midStr)>=0){
				that.longComSubstrArr.push(midStr);
			}
		}
	}
	// 如果本次没有找到最大字符串,进行下一个循环
	if(that.longComSubstrArr.length <=0 && ind<=that.smallLen){
		that.getSmallSonStr(ind+1);
	}
}

// 初始化
longComSubstr.prototype.initFunc=function(str1,str2){
	this.setSmallLarge(str1,str2);
}

// 开启处理
longComSubstr.prototype.dealFunc=function(){
	this.setSmallLen();
	this.getSmallSonStr(0);
}

// 获取结果 或者打印错误
longComSubstr.prototype.resultFunc=function(){
	if(this.longComSubstrArr.length>0){
		console.log(this.longComSubstrArr);
	}else{
		console.log('-1');
		// console.log(this.smallStr+'和'+this.largeStr+'没有公共子串');
	}
}

// 数组去重
longComSubstr.prototype.removeArrSameElement=function(){
	// var myArr = ['1','2','aa','ab','2','c','aa'];
	var myArr = this.longComSubstrArr || [];
	var newArr = [];
	// 当去重数组长度小于等于1时,不用处理
	if(myArr.length <= 1){
		this.longComSubstrArrNew = myArr;
		console.log(this.longComSubstrArrNew);
		return;
	}
	// 当去重数组长度大于1时
	for(var k=0,p=myArr.length;k<p;k++){
		if(newArr.length == 0 && k==0){
			newArr.push(myArr[k])
		}
		for(var k1=0,p1=newArr.length;k1<p1;k1++){
			if(myArr[k] == newArr[k1]){
				break;
			}
			if(myArr[k] != newArr[k1] && k1 == (newArr.length-1)){
				newArr.push(myArr[k])
			}
		}
	}
	this.longComSubstrArrNew = newArr;
	console.log(this.longComSubstrArrNew);
}
var myObj = new longComSubstr();
myObj.initFunc("1AB2451CDEF","2415CD3E4F");
myObj.dealFunc();
myObj.resultFunc();
myObj.removeArrSameElement();
原创,使用注明出处

全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期精华帖

热门推荐