Starry

发表于 更新于 分类于 本文字数： 148 阅读时长 ≈ 1 分钟

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
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
void nex(char *s, int *next)
{
    next[0] = 0;
    int now = 0, x = 1;
    while (x < strlen(s))
    {
        if (s[now] == s[x])
        {
            now+=1;
            next[x] = now;
            x += 1;
        }
        else if (now)
        {
            now = next[now - 1];
        }
        else
        {
            next[x] = 0;
            x += 1;
        }
    }
}

int kmp(char *s,char *p){
    int *next = NULL;
    next = (int *)malloc(sizeof(int) * strlen(p));
    nex(p, next);
    int now = 0, px = 0;
    while (now < strlen(s))
    {
        if (p[px] == s[now])
        {
            px += 1;
            now += 1;
        }
        else if (px)
            px = next[px - 1];
        else
            now += 1;
        if (px == strlen(p))
        {
            return 1;
        }
    }
    return 0;
}

int repeatedStringMatch(char * a, char * b){
char ans[1000000]="";
int res=0;
while(strlen(ans)<strlen(b)){
    strcat(ans,a);
    res+=1;
}
if(kmp(ans,b))
return res;
else strcat(ans,a);
res+=1;
if(kmp(ans,b))
return res;
else return -1;
}

发表于 更新于 分类于 本文字数： 115 阅读时长 ≈ 1 分钟 
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void nex(char *s, int *next)
{
    next[0] = 0;
    int now = 0, x = 1;
    while (x < strlen(s))
    {
        if (s[now] == s[x])
        {
            now += 1;
            next[x] = now;
            x += 1;
        }
        else if (now)
        {
            now = next[now - 1];
        }
        else
        {
            next[x] = 0;
            x += 1;
        }
    }
}


int main()
{
    char target[] = "dddcdabcddadcddadcddacddjaoabcdabcddadcddadcddacddababcddadabcdabcddadcddadcddacdddabcddadcddadcddacddadcdabcddadcddadcddacdddadcddacdabcddadcddadcddacdddcddadcddacddcabcddadcddadcddacddddadddadddcabcddadcddadcddacddabcddddabcddcabcddbaabcddbcabcddddcddd";
    char p[] = "dabcddadcddadcddacdd";
    int *next = NULL;
    next = (int *)malloc(sizeof(int) * strlen(p));
    nex(p, next);
    int now = 0, px = 0;
    while (now < strlen(target))
    {
        if (p[px] == target[now])
        {
            px += 1;
            now += 1;
        }
        else if (px)
            px = next[px-1];
        else
            now += 1;
        if (px == strlen(p))
        {
            printf("%d\n", now - px+1);
            px = next[px-1];
        }
    }
    return 0;
}

发表于 更新于 分类于 本文字数： 95 阅读时长 ≈ 1 分钟

再次验证我菜菜鸡

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
bool isPalindrome(char * s){
char strss[500000];
int x=0,y=0;
while(x< strlen(s)){
    if((s[x]>='a'&&s[x]<='z')||(s[x]>='0'&&s[x]<='9'))
        strss[y]=s[x];
    else if (s[x]>='A'&&s[x]<='Z')
        strss[y]=s[x]+'a'-'A';
    else {
        x++;
        continue;
    }
    y++;
    x++;
}
strss[y]='\0';
if(strlen(strss)==0||strlen(strss)==1)
return 1;
int len=strlen(strss);
x=0;
while(strss[x] == strss[len-x-1]){
    if(x==len/2)
    return 1;
    x++;
}
return 0;
}

发表于 更新于 分类于 本文字数： 54 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int searchInsert(int* nums, int numsSize, int target){
if(numsSize ==1){
    if(target<=nums[0])
        return 0;
    return 1;
}
int left=0 , right= numsSize,mid =numsSize/2;
while(right-left>1){
    if(target>=nums[mid])
        left = mid;
    else right = mid;
    mid=(left + right )/2;
}
if(target> nums[left])
    return right;
else return left;
}
0%