day21_常用类/07-尚硅谷-Java语言高级-String课后算法题目3

好，再来这个23题，其实还一般，难度一般，第四题呢，这个难度呢就要更大一些，CTRLC。看这个题说呢，获取两个字符串中的最大相同子串，这呢是个字符串，这个字符串看它俩里边呢，相同的这个字符串呢，最大的是多少啊，这个符号换成一个它的啊，那这个题目当中呢，我们这个大眼一看呢啊，有的同学呢，这个眼睛比较好使啊，直接能找到这个就是hello了，确实也没别的了啊，但是你这个时候呢，你就得想你是怎么看出来的。就是很多时候呢，咱们解决这种算法问题呢，大家呢，先把它就当成是一道像数学题一样啊啊这个数学题的话呢，你想想你你你是怎么解的是吧？啊那其实我们编程很多时候呢，都是你把这个数学题你的一个想法呢，给他用代码去实现就可以了，很多时候都是这样子的啊当然有些时候呢，呃，可能不太一样，你像这道题呢，就稍微有点区别，就是大家呢，你说你怎么找出来，Hello，很难说是吧。

就人呢，可能挺善于去这两个一看呢，找到一些相同的或者不同的了，所以专门有个游戏呢，就要找不同是吧。对，这就属于一类游戏了，哎，让你看这个眼神了哈，那这个的话呢，相当于让你找相同的，大家可能就一下子就是一看就感觉这块呢，稍微有点感觉，哎，然后呢，这个先，比如说你先看到是lo吧，哎，这个找到以后呢，你会再往边上去扩一下，一扩诶发现诶竟然还有个hello，如果呢，你要发现还有另外一个也有点一样的，你再一扩发现那个比这个还长啊，那就以那个为准。嗯，当然你这个你你是很随意的找了一个LL，呃跟这去找的是吧，这个你要用咱们这个算法来写这个事就很难实现了，这个就很难找了，是吧，除非呢，你用这个深度学习人工智能了，他帮你去找的时候呢，当然他就找不管能找这个字符串了，它就能够给你去找这个图片了，嗯，它就能去找图片了，哎看到其中的某一块这个数据呢，它是比较接近的，那它就直接呢就定位到这块了。

哎，用不着从头这样一点点点去比了，是吧，那但咱这毕竟这个这个得自己来亲自写了啊，并不是人工智能了啊，那这个题有点难度，先把这个声明呢先写出来，找到它们的最大相同子串，那返回的是一个string啊，Get一个max最大的嗯，相同的啊是一个字符串，这样来写吧，这呢两个磁符串呢，还有地位的区别吗？

没有了，就是找它俩的最大相同字块，谁先写谁后写无所谓，嗯嗯，那这呢，我们暂时呢，先return一个now这个题目怎么做？先拆，嗯嗯，怎么拆啊，你就说啊，这这有个长的有个短的，找这个短的是吧，一个。嗯，行，刚才提到有这样的思路，如果找个这个短的，因为你俩这个最大强度子段它肯定不会超过这个短的了，那找这个短的，然后刚才提到说那我就先找一个啊，现在你把这个字符串呢，一个一个的取是吧，比如我找一个的，先找个C，看这边有没有啊，有有有怎么办？有就别再去单独找个V了。

但是也不好说，假设呢，你这个就最大的相对就是长度是一，长度是一的话呢，说白了就是这个不止一个是吧，C可能有一个或头还有一个，比如一个N的。这个题目的话呢，咱们先暂时啊，咱们先降低下的难度，先暂时呢，认为它最大的相同子串呢，就只有一个啊，就只有一个，就像这个题目的hello啊，就我们就不整，比如说后边这个ABCDEF，这个我也有一个ABCDEF啊，这呢相当于是有两个最大相同字串，就是一个是hello，一个是ABCDEF，咱们先不考虑这种情况啊，先只考虑只有一个啊只有一个的情况。你要是有多个，这就得四轮数组了啊，那你要是有一个的时候呢，刚才提到说我就先找一个的，一个要找到了，一个找到了你肯定这个不一定是，可能还有两个的，两个呢，找到了也不行，还有三个的，三个不行，可能还有四个的。

那找到什么时候终止呢？把它的length长度都找完，都找完以后呢，这时候你还得往回返，因为你找完以后你才知道最大的长度的假设不行，再往回减一个的，再减两个的，减三个的，其实你这个效率呢，不会特别高。诶听到有个同学说我们先从长的往短里边找，对吧？嗯，这个呢，思路呢，我们以前涉及到过，咱们以前讲说这个12，比如说16，它们两个的最大公约数。最大公约数，咱们当时找的时候，你是从一开始找的吗？不对呀，是吧，咱们是不是从12开始往下递减的找啊。嗯，最大公因数不会超过它的，就跟说你这个它俩的最大相同子串，它也不会超过这个短的的，所以我们从这个12开始找，12不行了，看11 11不行了，看十，诶突然有一个呢，可以了，停，不要再往下找了，你要从下往大找，你找了一找二找三找四，白找是吧，找了可能后边竖着了，前面你就不用没意义，所以呢，我们这个题目也是从这个长长的啊对，再往短里找，沿IG呢，就是我们先拿着这个短的看看它在不在这里边。

咱们可以调一个string的方法，叫contents对吧，判断呢，它在不在这里边，如果在那就幸福了，他就是，嗯，这就是那大部分情况下可能都不在，那不在怎么办？对这个长度不行了，然后得剪一个是吧，那剪一个呢，就相当于取这个的字符串的一个子串了，这个子串呢，长度少一个的呢，其实有两种情况，对一个是这个是吧？啊一个呢是把前面这个抛出去，要这个，那你这两个都得考虑一下，那还不在再减，再减的话，那就得是这是一个，然后再往后移一下，这是一个啊再往后移一下，这是一个，相当于咱们就定义两个指针，对这两个指针呢，就是控制一下这个，一个是当头一个当尾，然后呢，我们去取这个串的一个sub磁针。

这个指针的话呢，这就涉及到呃，这个一开始咱们其实就相当于是第一大轮了哈。第一大轮的话呢，这个指针头部就在头，尾部就在尾，相当于是你这个字符串本身，然后这是第一大轮，如果没有是不是还有第二大轮，第二大轮就是让这个他俩的这个这个就这个长度，相当于是抠出去一个是吧，这是第二大轮，然后第三大轮呢，就抠出去俩，第四大轮呢，抠出去仨啊依次这样。啊，那么你就是抠出去一个的时候呢，咱们也看到了，里边呢又有两种情况了，相当于你这这是大轮哈，呃，是一个循环，然后具体抠出去一个的时候呢，发现又有两种情况，抠出去三个呢，情况更多，里边呢是不是还有一个for，哎，所以这个题目呢，就得是两层for才可以。

啊，只要呢，你在某一层for当中，比如我抠出去三个的时候啊，For的时候呢，发现诶找到了content的时候是触了，就不用在后边去考虑这些了。就这样的一个大体的思路嘛，嗯，行，那咱们来解决，这里边呢，虽然对STR1和二的他们这个位置没有要求，但是他们两个的这个谁长谁短啊，还是有要求的，因为咱们要拿着这个短的去比啊，就像求这个最大公间数一样，我们这里边先去判断一下它俩里边谁短，那就是str1.lengths，它呢如果大于。大于等于吧，诶大于it t22.length哎，如果是这样子的话，哎，我们呢，返回叫it tr1，否则it t2这个呢，我们得到一个string，这个呢叫一个max string。

哎，这是它，然后呢，我们再对应的得到一个叫min的itr。H21第二，但它呢，如果要是小于这个等号，还加不加呢，想想。就是你别最后整的这个，有的时候你得体会一下啊，别最后整的，那这两个整出来以后都是STR1了，长度一样的话呢，结果取都是HR1，那就不行了啊，那先考虑这种比较通俗的情通，通常的情况就是这个它的长度长，它的长度短，那这个时候呢，就是取的是这个长的。这个呢，取的是这个短的，这个时候呢，你加不加等号呢，好像没什么区别。反正它俩长度不一样嘛，啊，这个取的是这个短的，这没问题，那如果说这两个呢，恰好长度一样，它俩长度一样，你这就是个处，咱们把二一给返回了，这俩长度一样，我是不是又把HT21给返回了，那这个位置是不是就不要加啊，这个细微的问题大家也要考虑到，这种事呢，你要是觉得这是最简单的，写完以后回头一挑，发现老是出错是吧？哎，这样细微体会一下啊，那么这样的话呢，咱们就把它们两个谁长谁短取出来了，好，下边呢，咱们开始写循环。

刚才呢提到得有两轮啊，外层这个呢是一大轮是吧，说第一大轮一个也不去，拿着一个短的一个也不去，第二大轮去一个，第三大轮去三个啊，去四个去五个，那么想一想一共需要进行多少大轮？这个咱们就拿一个小例子来体会一下，比如说我们这个是ABC吧，这个呢比较长，看看这个ABC在这里边呢，出现了几次，哎，我们第一大轮是不是一个也不去，第二大轮去一个，第三大轮呢去两个。

啊，第三大轮去两个，还有第四大轮吗？第三大轮去三个，去三个那就没有了，没有你去判断没啥意思了是吧？所以这块呢，如果是有三个长度，是不是就三大轮，那我们这呢，是不是就知道诶in一个length就等于M。it2.less，所以这块呢，我们就哎int I等于零，I呢小于less就可以了啊，I加加，这是Y层的这个多少大轮这里跟上这个节奏啊，这一掉队的话呢，一会儿就不好这个这个跟进了，呃，那么这是几大轮，每一轮呢，我们考虑呢，就是去一个去一个这个这个这个长度去比啊，那么对于第一大轮来讲，咱们先写第一大轮的这个可能还好一点哈，第一大轮的话呢，好像就不用刻意的去写这个for循环了，直接在里边比就完了，第一大轮嘛，我们相当于就是比一下谁呢？我们这个叫max itr，它呢contains这个叫me itr了，第一大轮，第一大轮如果这样的话呢，它是一个处，那咱们这时候返回的就是这个幂H2了，就剩它了是吧，这第一大轮好说。

那么第二大轮的话呢，你就不能每次判断的是它了，应该是我们这个的一个子串。是吧，哎，是它的一个子串了啊，它这个子串呢，你就这个位置，我们得写一下吧，它的一个叫subs string subs string呢，你得有一个头，有一个尾啊，有头有尾，那这个头尾呢，我们需要在这里边去定义了啊，这是X一个，然后尾呢是一个，然后呢，这个嗯，还得有一个这个循环条件，还得有一个迭代条件。

啊，这个X多少呢，先让它是头这个Y呢，对于咱们第一次来讲啊，第一轮来讲，第一轮来讲，其实就是我们这个他点L呗。嗯，第一轮嘛，对吧，那么这个subs这不就写个零，嗯，写个X写个Y，这呢取出来它的它的这个叫subst string。哎，String，哎，这个我叫sub str叫它了，然后这块CTRLC是不是比的是它呀，哎如果要有就返回给它呗。理解是吧？没问题吧，那么接着的话，你得考虑就是可能第一轮呢没找到啊，第一轮没找到，你考虑第二轮的时候呢，第二轮咱们就先呢，考虑的是这个长度了，这个长度的话呢，你这个X还是零，但是Y呢不是尾了。

Y呢，也相当于是尾是不是往前抠一个，哎，那第三大轮是不是就第三大轮头是不是得扣俩，相当于我在这个位置呢，减去一个I，正好第一轮I就是零，第二轮抠一个是吧？这样啊，那么相当于这个呢，我们减A就是有可能它，诶某一次的这个某一大轮的开头呢，是这个，那这个要判断不行，是不是让这个X和Y都往后加个一错一位就行，对吧？所以我们这个呢，诶迭代条件等于X加加，Y呢加加，那这个终止条件是什么。Y呢，得小于等于。就是咱们这边是你，你比如说这个开头的某一轮的哈，开头是它，然后呢，再接着呢，就是这个往后错一个，再往后错，再往后错，你错到末尾的就是这个Y呢，是不是取到它就不能再往后错了，那它呢，呃，这我们因为subs这个位置呢，取不到嘛，所以我这写成这个A。

有等号不没有。有吧，有吧。让这个Y呢，取到这个LS，然后我这个呢，还这块不是不要这个LS吗？正好LS减一就是正好是最后一个索引嘛。这个得有对吧。这个是有点难度啊，那这样的话呢，我们就这个每一轮啊去取这一段，然后这个呢，看看取出来有没有，如果要是没有没有呢，我们再整个再往后错一下，再看有没有没有再错再错，哎，这一轮当中到尾部了，看看有没有，如果说找到了，我们这会return啊，这个return呢是来结束方法的，整个相当于出去了啊，这挺好的啊嗯，那么还有没有别的情况呢，始终找找找找找，一直呢这块呢，这个也没找到，那就爱加加还始下一大轮，然后整个这个循环完以后呢，也还没找到，那相当于他们就没有最大相当串，我就return no就这样处理了，行，那这个题目呢，其实就主体上就结束了啊，当然了，这里边你要为了保证这个题目的一个这个这个安全性啊，就是这个健壮性这里呢，我们去调LAS啊，前提是它俩都不能是no。

对吧，你这个也可以在最初的时候呢，我们加上一个判断，如果IR1它不等于no。哎，他呢，不是闹。哎，我们呢，做这样的一个判断，那你要是闹了这块呢，我们其实可以把它呢，就这样拿一下就得了，啊是闹的话呢，这个你就直接闹一下得了，嗯，洗完以后呢，我们测试一下。

Test get marks。的一个词。诶，这个呢，我们string的STL1，诶等于，诶不妨呢，咱们就拿它来说CTRLC，诶CTRLV一下。好，然后呢，我们来调这个方法，CTRLC在这这个呢，谁先谁后无所谓，得到一个最大的相同子串。输出一下看看对不对。哎，Hello出来了，那我们这块呢，再处理一下，比如hello这个位置我写个一啊，这个也写个一。那也也行，那通过这样测试呢，这个倒是都对的啊，你再测一下其他的情况也OK，那这个的话呢，我们相当于就做完了，但是这个题目的话，咱们有一个前提啊。

前提呢，就是我们这两个字符串中，对只有一个最大相同字串。就长度一样的，这个就只有一个。