05 August 2008
给定一个字符串 s，检查它是否可以通过获取它的一个子字符串并将该子字符串的多个副本附加在一起来构造。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public boolean repeatedSubstringPattern (String s )
{
int i=0;
for(int j =i+1;j <= s.length()/2;j++)
{
StringBuilder sub1 = new StringBuilder(s.substring(i,j));
StringBuilder sub2 = new StringBuilder(s.substring(j,s.length()));
sub2.append(sub1);
if (sub2.toString().equals(s))
{
return true;
}
}
return false;
}
}
KMP
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
class Solution {
public boolean repeatedSubstringPattern(String s)
{
// Using the KMP prefix
int[] next = new int[s.length()];
getNext(next, s);
if (next[s.length() - 1] != -1 && s.length() % (s.length() - 1 - next[s.length() - 1]) == 0)
return true;
return false;
}
public void getNext(int[] next, String s)
{
// aabaaf -> -1,0,-1,0,1,-1;
// aabaabf -> -1,0,-1,0,1,2,-1
// aabaabaab -> -1,0,-1,0,1,2,3,4,5
next[0] = -1;
int j = -1;
for (int i = 1; i < s.length(); i++)
{
while (j >= 0 && s.charAt(i) != s.charAt(j + 1))
j = next[j];
if (s.charAt(i) == s.charAt(j + 1))
j++;
next[i] = j;
}
}
}