algo-aha

A循环移位可得B <=等价于=> B是AA的子串

• https://leetcode.com/problems/rotate-string

1. A循环移位得到的串都是串AA的子串，故B是AA的子串。
2. B是AA的子串，假设在A|A拼接处B被分成B1|B2，A的后半段是B1、前半段是B2，A=B2|B1，A循环移位可得B。

s=pattern*k <=等价于=> (s+s).find(s,1) < s.size()

设d=(s+s).find(s,1)，则pattern=s.substr(0,d)，k=s.size()/d。

想象将s串平移一小段后仍与原串重叠，平移距离就是pattern长d。

直观上，记两串s1|s2、平移距离d（对应模式子串P）、平移后两串s1'|s2'：
1. s1'末尾的P==s2开头的P、故s1末尾的P==s1开头的P
2. s1'开头的P==s1第二个P、故s1开头的P==s1第二个P
3. s1'第二个P==s1第三个P、故s1第二个P==s1第三个P，以此类推...

联系：最短长度编码字符串

从目录结构串中找最长绝对路径

• https://leetcode.com/problems/longest-absolute-file-path/

int lengthLongestPath(string input) {
    istringstream iss(input);
    string line;
    stack<int> stk;
    int ans = 0;
    while (getline(iss, line)) { // 遍历\n每行路径，并将绝对路径长压栈
        int indent = 0;
        while (line[indent] == '\t') indent++;
        while (stk.size() > indent) stk.pop(); // 父目录数等于缩进数
        int filelen = line.size() - indent;
        int pathlen = (stk.empty() ? 0 : stk.top() + 1) + filelen; // 1是分隔符长
        stk.push(pathlen);
        if (line.find(".") != string::npos) ans = max(ans, pathlen);
    }
    return ans;
}