字符串的最大公因子

对于字符串 s 和 t，只有在 s = t + t + t + … + t + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。

  • 输入：str1 = “ABCABC”, str2 = “ABC”
    输出：”ABC”

  • 输入：str1 = “ABABAB”, str2 = “ABAB”
    输出：”AB”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
var gcdOfStrings = function(str1, str2) {
    const m=str1.length;
    const n=str2.length;
    let t='';
    let j=1;
    let maxlen=0;
    let str=str1;
    let min=n
    if(m<n)
    {
        str=str2;
        min=m
    }
    for(;j<=str.length;j++)
    {
        if(str[j]===str[0])
        {
            let pat=str.substring(0,j);
            if(j===min-1)
                pat=str.substring(0,j+1);
            const len=pat.length;
            if((m%len!==0)||(n%len!==0))
                continue;
            const x=m/len;
            const y=n/len;
            if(str1===pat.repeat(x)&&str2===pat.repeat(y))
            {
                const r=gcd(Math.max(x,y),Math.min(x,y))
                t=pat.repeat(r);
                break
            }
        }
    }
    function gcd(m,n)
    {
        if(m%n===0)
            return n
        return gcd(n,m%n)
    }
    return t
};