匹配圆周率题 求助大神

寂寞知己

求助大神！   研究到哭  也是错误，网上搜不到~

jackz007

#include <stdio.h>

int match(char s1[] , char s2[])
{
        int i , j , m , n , r = -1                                             ;
        for(m = 0 ; s1[m] ; m ++)                                              ;
        for(n = 0 ; s2[n] ; n ++)                                              ;
        if(m >= n && n > 0) {
                for(i = 0 ; i < m - n + 1 ; i ++) {
                        for(j = 0 ; j < n ; j ++) if(s1[i + j] != s2[j]) break ;
                        if(j == n) {
                                r = i                                          ;
                                break                                          ;
                        }
                }
        }
        return r                                                               ;
}

int main(void)
{
        char s1[1000000] , s2[1000000]  ;
        scanf("%s" , s1)                ;
        scanf("%s" , s2)                ;
        printf("%d\n" , match(s1 , s2)) ;
}

        编译、运行实况：

D:\00.Excise\C>g++ -o x x.c

D:\00.Excise\C>x
1234
1234
0

D:\00.Excise\C>x
1234
12345
-1

D:\00.Excise\C>x
821999052039574422
19990520
2

D:\00.Excise\C>x
881994082555083527588321827035
19940825
2

D:\00.Excise\C>

傻眼貓咪

#include <stdio.h>

int match(char A[], char B[]){
    for(int i = 0; A[i]; i++){
        if(A[i] == B[0]){
            int check = 1;
            for(int j = i, n = 0; B[n]; j++, n++){
                if(B[n] != A[j]){
                    check = -1;
                    break;
                }
            if(check) return i;
            }
        }
    }
    return -1;
}

int main(){
    char A[1000000], B[1000000];
    scanf("%s", A);
    scanf("%s", B);
    int answer = sizeof(A) >= sizeof(B) ? match(A, B) : -1;
    printf("%d", answer);
}

100gram

寂寞知己

jackz007 发表于 2021-11-13 22:45
编译、运行实况：

最后的测试点显示超时，可能有些问题

寂寞知己

傻眼貓咪 发表于 2021-11-14 09:35

部分正确，有2个测试点不正确

傻眼貓咪

寂寞知己 发表于 2021-11-14 20:06
部分正确，有2个测试点不正确

已修改：

#include <stdio.h>

int match(char A[], char B[], int N, int M){
    for(int i = 0; i < N-M+1; i++){
        if(A[i] == B[0]){
            int check = 1;
            for(int j = i, n = 0; B[n]; j++, n++){
                if(B[n] != A[j]){
                    check = -1;
                    break;
                }
            if(check) return i;
            }
        }
    }
    return -1;
}

int main(){
    char A[1000000], B[1000000];
    scanf("%s", A);
    scanf("%s", B);
    int a, b;
    for(a = 0; A[a]; a++){}
    for(b = 0; B[b]; b++){}
    int answer = a > b ? match(A, B, a, b) : -1;
    printf("%d", answer);
}

阿萨德按时

寂寞知己

傻眼貓咪 发表于 2021-11-14 20:57
已修改：

还是3个错误点。。。。。。

傻眼貓咪

寂寞知己 发表于 2021-11-15 21:08
还是3个错误点。。。。。。

抱歉，有没有可以参考的参数？

1molHF

寂寞知己

傻眼貓咪 发表于 2021-11-15 21:13
抱歉，有没有可以参考的参数？

只有这个。。。。。


第一个人是对的   只不过最后那个测试点显示超时，你这个借鉴下第一个人   把超时整没有了   应该就是正确答案啦

傻眼貓咪

寂寞知己

jackz007 发表于 2021-11-13 22:45
编译、运行实况：

这个超时能解决一下吗？

jackz007

寂寞知己 发表于 2021-11-15 22:17
这个超时能解决一下吗？

        那就再试试这个？

#include <stdio.h>

int main(void)
{
        char s1[1000000] , s2[1000000]                                         ;
        int i , j , k = -1 , m , n                                             ;
        scanf("%s" , s1)                                                       ;
        scanf("%s" , s2)                                                       ;
        for(m = 0 ; s1[m] ; m ++)                                              ;
        for(n = 0 ; s2[n] ; n ++)                                              ;
        if(m >= n && n > 0) {
                for(i = 0 ; i < m - n + 1 ; i ++) {
                        for(j = 0 ; j < n ; j ++) if(s1[i + j] != s2[j]) break ;
                        if(j == n) {
                                k = i                                          ;
                                break                                          ;
                        }
                }
        }                
        printf("%d\n" , k)                                                     ;
}

寂寞知己

jackz007 发表于 2021-11-15 22:49
那就再试试这个？

还是超时。。。。。。。。。。。。。。

jackz007

寂寞知己 发表于 2021-11-15 22:51
还是超时。。。。。。。。。。。。。。

            这个呢？

#include <stdio.h>

int main(void)
{
        char c , s1[1000000] , s2[1000000]                                     ;
        int i , j , k = -1 , m , n                                             ;
        for(m = 0 ; (c = getchar()) != '\n' ; m ++) s1[m] = c                  ;
        for(n = 0 ; (c = getchar()) != '\n' ; n ++) s2[n] = c                  ;
        if(m >= n && n > 0) {
                for(i = 0 ; i < m - n + 1 ; i ++) {
                        for(j = 0 ; j < n ; j ++) if(s1[i + j] != s2[j]) break ;
                        if(j == n) {
                                k = i                                          ;
                                break                                          ;
                        }
                }
        }                
        printf("%d\n" , k)                                                     ;
}

寂寞知己

jackz007 发表于 2021-11-15 22:59
这个呢？

还是超时。。。。。。。。       最后那个检测点超时 ，应该还是算法出了问题，有某处跟题不符合吧。。

傻眼貓咪

寂寞知己 发表于 2021-11-15 23:02
还是超时。。。。。。。。       最后那个检测点超时 ，应该还是算法出了问题，有某处跟题不符合吧。。

这已经是我的极限了，希望不会错：

#include <stdio.h>

int kmp(char S[], char W[], int s, int w){
    int P[s], nP = 0, j = 0, k = 0, T[s];
    for(int i = 0; i < s; i++){
        T[i] = -1;
        P[i] = -1;
    }
    while(j < s){
        if(W[k] == S[j]){
            j++;
            k++;
            if(k == w){
                P[nP] = j-k;
                nP++;
                k = T[k];
            }
        }
        else{
            k = T[k];
            if(k < 0){
                j++;
                k++;
            }
        }
    }
    for(int i = 0;; i++){
        if(P[i] > 0){
            return P[i];
        }
    }
}

int main()
{
    char A[1000000], B[1000000];
    scanf("%s", A);
    scanf("%s", B);
    int a, b;
    for(a = 0; A[a]; a++){}
    for(b = 0; B[b]; b++){}
    int answer = a > b ? kmp(A, B, a, b) : -1;
    printf("%d", answer);
}

jackz007

寂寞知己 发表于 2021-11-15 23:02
还是超时。。。。。。。。       最后那个检测点超时 ，应该还是算法出了问题，有某处跟题不符合吧。。

        题目要求使用 KMP 快速模式匹配，我在网上抄了一段代码，现在再试试呢

#include <stdio.h>

void Next(char * T , int * next)
{
        int i = 1 , j = 0 , m                        ;
        next[1] = 0                                  ;
        for(m = 0 ; T[m] ; m ++)                     ;
        while(i < m) {
                if(j == 0 || T[i - 1] == T[j - 1]) {
                        i ++                         ;
                        j ++                         ;
                        next[i] = j                  ;
                } else {
                        j = next[j]                  ;
                }
        }
}

int KMP(char * S , char * T)
{
        int i = 1 , j = 1 , next[10] , m , n         ;
        for(m = 0 ; S[m] ; m ++)                     ;
        for(n = 0 ; T[n] ; n ++)                     ;
        Next(T , next)                               ;
        while(i <= m && j <= n) {
                if (j == 0 || S[i - 1] == T[j - 1]){
                        i ++                         ;
                        j ++                         ;
                } else {
                        j = next[j]                  ;
                }
        }
        if(j > n) return i - n - 1                   ;
        else return -1                               ;
}

int main(void)
{
        char c , s1[1000000] , s2[1000000]                   ;
        int m , n                                            ;
        for(m = 0 ; (c = getchar()) != '\n'; m ++) s1[m] = c ;
        for(n = 0 ; (c = getchar()) != '\n'; n ++) s2[n] = c ;
        s1[m] = s2[n] = '\0'                                 ;
        printf("%d\n" , KMP(s1, s2))                         ;
}