图片说明

T.size==S.size||T.size>S.size

一个串给一个指针,算出最大的相同子串长度

枚举改变T的指针的起始位置

S串指针从后开始移动(因为不能从后删除)

显然T串的指针也是从后开始移动废话

  • 操作3
  • 操作2
  • 操作1
  • 这三步算法其实就是下面的ans算法

aaaaaaaaabbbbbbcccccc T

​ aaabbb S

ans=T.size+S.szie-末尾最大匹配数*2(都从后往前扫)

匹配情况不应该为

aaaaaaaaabbbbbbcccccc T

​ aaabbb S

T.size<S.size

  • 1

​ aaaaaa T

(操作3)bbbbbbbbaaa (操作2) S

操作2,操作3

换成末尾匹配的话

​ aaaaaa T

(操作3)bbbbbbbbaaa (操作2) S

这不就是3吗....

  • 2

​ aabbbb T

aaaaaabbbbbbbcccccddd s

ans=T.size+S.szie

进一步思考有3

  • 3

​ aabbbb T

aaaaaabbbbbbbccccccbb s

ans=T.size+S.szie-末尾最大匹配数*2(都从后往前扫)