字符串的左旋转

Question

我需要通过n个元素旋转大小为d字符串的给定字符串。例如

Let's assume S is the input string = "apple" 
d = 2 
Output N after the left rotation = "pleap"

我需要提出一种计算N的Turing Machine算法。

我正在考虑的一种算法：

1. 移至磁带开头的开头，并用空白替换第一个符号
2. 移至磁带的末尾并在其中移动符号
3. 倒回到状态的开头并重复吗？

这项工作吗？如何提出可以解决此问题的车床？

Answer 1

我的图灵机当前损坏（内存不足，但是...

当手头有一个旋转的数组并想使其不旋转时，有一个古老的技巧。

说旋转的字符串是CDEAB

您可以通过首先将部分向上反转到头部（此处为CDE，然后从头部到末端的部分（此处为AB，然后是整个对象）来还原原始字符串。

首先CDEAB-> EDCAB

然后EDCAB-> EDCBA

最后EDCBA-> ABCDE

此原理同样适用于从未旋转到旋转。

因此，对于apple，rotate=2，我们会这样做

左后方ap-> pa

右后部分ple-> elp

全部反转paelp-> pleap

这应该很容易在类似图灵的机器上实现。