# javascript - 如何检查字符串是否完全由相同的子字符串组成?

## string algorithm (8)

C ++实现参考：

``````vector<int> z_function(string s) {
int n = (int) s.length();
vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; ++i) {
if (i <= r)
z[i] = min (r - i + 1, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];
if (i + z[i] - 1 > r)
l = i, r = i + z[i] - 1;
}
return z;
}``````

JavaScript实现

``````function z_function(s) {
var n = s.length;
var z = Array(n).fill(0);
var i, l, r;
//for our task we need only a half of z-array
for (i = 1, l = 0, r = 0; i <= n/2; ++i) {
if (i <= r)
z[i] = Math.min(r - i + 1, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];

//we can check condition and return here
if (z[i] + i === n && n % i === 0) return true;

if (i + z[i] - 1 > r)
l = i, r = i + z[i] - 1;
}
return false;
//return z.some((zi, i) => (i + zi) === n && n % i === 0);
}
console.log(z_function("abacabacabac"));
console.log(z_function("abcab"));``````

``string s= 'abacabacabac'  with length n=12```

z-array是

``(0, 0, 1, 0, 8, 0, 1, 0, 4, 0, 1, 0)``

``````i=4
i+z[i] = 4 + 8 = 12 = n
and
n % i = 12 % 4 = 0```````

``````"aa" // true(entirely contains two strings "a")
"aaa" //true(entirely contains three string "a")
"abcabcabc" //true(entirely containas three strings "abc")

"aba" //false(At least there should be two same substrings and nothing more)
"ababa" //false("ab" exists twice but "a" is extra so false)``````

``````function check(str){
if(!(str.length && str.length - 1)) return false;
let temp = '';
for(let i = 0;i<=str.length/2;i++){
temp += str[i]
//console.log(str.replace(new RegExp(temp,"g"),''))
if(!str.replace(new RegExp(temp,"g"),'')) return true;
}
return false;
}

console.log(check('aa')) //true
console.log(check('aaa')) //true
console.log(check('abcabcabc')) //true
console.log(check('aba')) //false
console.log(check('ababa')) //false``````

``````IsRepeatedQ[list_] := Module[{n = [email protected]},
[email protected]@Sum[list[[i]] Exp[2 Pi I i/n], {i, n}] == 0
];``````

``````hello (the trivial rotation)
elloh
llohe
lohel
ohell ``````

``````hellohello
^^^^^``````

``````function check(str) {
return (str + str).indexOf(str, 1) !== str.length;
}``````

``````'ababababa'.replace(/ab/gi,'')
"a" // return false
'abababab'.replace(/ab/gi,'')
""// return true``````

``````function check(str) {
t = str + str;
find all overlapping occurrences of str in t;
for each occurrence at position i
if (i > 0 && i < str.length && str.length % i == 0)
return true;  // str is a repetition of its first i characters
return false;
}``````

L：原始字符串的长度

S：有效子字符串的潜在长度

``````function* primeFactors (n) {
for (var k = 2; k*k <= n; k++) {
if (n % k == 0) {
yield k
do {n /= k} while (n % k == 0)
}
}
if (n > 1) yield n
}

function check (str) {
var n = str.length
primeloop:
for (var p of primeFactors(n)) {
var l = n/p
var s = str.substring(0, l)
for (var j=1; j<p; j++) {
if (s != str.substring(l*j, l*(j+1))) continue primeloop
}
return true
}
return false
}``````

``````function check (str) {
var n = str.length
for (var p of primeFactors(n)) {
var l = n/p
if (str.substring(0, n-l) == str.substring(l)) return true
}
return false
}``````

``````def checkString(string):
gap = 1
index= 0
while index < len(string)/2:
value  = [string[i:i+gap] for i in range(0,len(string),gap) ]

x = [string[:gap]==eachVal for eachVal in value]

if all(x):
print("THEY ARE  EQUAL")
break

gap = gap+1
index= index+1

checkString("aaeaaeaaeaae")``````