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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| void nex(int *next, char *s)
{
next[0] = 0;
int now = 0, j = 1, lens = strlen(s);
while (j < lens)
{
if (s[now] == s[j])
next[j++] = ++now;
else if (now)
now = next[now - 1];
else
next[j++] = 0;
}
}
int *findSubstring(char *s, char **words, int wordsSize, int *returnSize)
{
int wordlen = strlen(words[0]), lens = strlen(s), has = wordsSize * (wordsSize + 1) * (2 * wordsSize + 1) / 6, i = 0;
int *next = (int *)malloc(sizeof(int) * wordlen), *t = (int *)malloc(sizeof(int) * lens), *result = (int *)malloc(sizeof(int) * lens);
int j = lens;
while (j--)
{
t[j] = 0;
result[j] = -1;
}
while (i < wordsSize)
{
nex(next, words[i]);
int now = 0, s1 = 0;
while (s1 < lens)
{
if (words[i][now] == s[s1])
{
now += 1;
s1 += 1;
}
else if (now)
now = next[now - 1];
else
s1 += 1;
if (now == wordlen)
{
t[s1 - now] = (i + 1) * (i + 1);
now = next[now - 1];
}
}
i += 1;
}
i = 0;
int answernum = 0;
while (i < lens)
{
int hanow = 0;
if (t[i])
{
hanow += t[i];
int z = i + wordlen, step = 1;
while (step < wordsSize && z < lens && t[z])
{
hanow += t[z];
z += wordlen;
step += 1;
}
if (hanow == has)
{
result[answernum] = i;
answernum += 1;
}
}
i += 1;
}
*returnSize = answernum;
if (answernum == 0)
return NULL;
int n = 0;
int *res = (int *)malloc(sizeof(int) * answernum);
while (answernum--)
{
res[n] = result[n];
n += 1;
}
return res;
}
|