如何检查一个字符串是否是另一个字符串的循环旋转？

Question

如何在R中检查给定字符串是否为另一个给定字符串的循环旋转？例如： 1234 通过两次偏移是 3412 的循环旋转。但我想检查一个字符串是否与另一个字符串在任意数量的移位下循环等价。

- user251385

---

不确定它有多健壮，但你可以尝试复制每个向量并使用 grepl 函数匹配另一个向量，或者使用 grepl(y, strrep(x, 2)) || grepl(x, strrep(y, 2)) 的替代方法。 - alexis_laz

@alexis_laz 不错！对于你的第一个建议，nchar的检查是否足够呢？ nchar(x) == nchar(y) & grepl(pattern = y, x = strrep(x, 2))。想发表一篇答案吗？ - Henrik

Answer 1

根据Henrik的评论，测试(i) nchar是否相等以及(ii)如果一个向量在复制第二个后成为其一部分似乎是足够的：

ff = function(x, y) (nchar(y) == nchar(x)) && (grepl(y, strrep(x, 2), fixed = TRUE))

ff("3412", "1234")
#[1] TRUE

- alexis_laz

---

这个不错！复制字符串是关键，让正则表达式引擎完成所有工作。比自己创建所有可能的循环旋转要好得多。 - Uwe

@UweBlock：我认为这里的主要缺点是，如果“x”非常大，而strrep无法分配所需的内存。 - alexis_laz

可用内存可能不是首先达到限制的限制。 “Memory-limits”说：“字符字符串中的字节数限制为2 ^ 31-1〜2 * 10 ^ 9”。因此，如果y的长度最大，则x只能有一半的字节。总共，x和y可以拥有最多3 * 10 ^ 9个字节，大约相当于3 GB的内存。也许，Unicode可能需要更多的内存，但可用内存可能不是您方法的阻碍者。 - Uwe

Answer 2

你可以一直生成旋转，直到找到匹配的字符串。如果没有旋转匹配，则这些字符串不是彼此的循环旋转。使用 sub 解决方案：

cycrotT = function(s1,s2) {
  if (nchar(s1)!=nchar(s2)) {
    return(FALSE) }
  for (i in 1:nchar(s2)) {
    if (s1==s2) {
      return(TRUE) }
    # Move the first character to the end of the string
    s2 = sub('(.)(.*)', '\\2\\1', s2)
  }
  return(FALSE)
}


> cycrotT("1234567", "1324567")
# [1] FALSE
> cycrotT("1234567", "4567123")
# [1] TRUE
> cycrotT("1234567", "1234568")
# [1] FALSE

- sirallen

---

目前似乎通过了所有测试，但它只是代码而已。加入一些解释，它就值得点赞了。 - IRTFM

Answer 3

一种更长但或许更清晰的方法如下：

cyclic_index <- function(string1, string2) {

  ## gather info about the first string
  chars <- el(strsplit(string1, ""))
  length <- length(chars)
  vec <- seq_len(length)

  ## create a matrix of possible permutations
  permutations <- data.frame(matrix(NA, nrow = length, ncol = length + 1))
  names(permutations) <- c("id", paste0("index", vec))

  permutations$id <- vec

  ## calculate the offset indices
  for (r in vec)
    permutations[r, vec + 1] <- (vec + r - 1) %% (length)

  ## a %% a = 0 so reset this to a
  permutations[permutations == 0] <- length

  ## change from indices to characters
  permutations[ , vec + 1] <- sapply(vec, function(x) chars[unlist(permutations[x, vec + 1])])

  ## paste the characters back into strings
  permutations$string <- sapply(vec, function(x) paste0(permutations[x , vec + 1], collapse = ''))

  ## if string2 is a permutation of string1, return TRUE
  return(string2 %in% permutations$string)

}

cyclic_index("jonocarroll", "carrolljono")
#> TRUE

cyclic_index("jonocarroll", "callorrjono")
#> FALSE

cyclic_index("1234567", "4567123")
#> TRUE

- Jonathan Carroll