论坛 › 数据结构与算法 › 匹配圆周率题 求助大神

寂寞知己 发表于 2021-11-13 22:17:30

匹配圆周率题 求助大神

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

jackz007 发表于 2021-11-13 22:45:31

#include <stdio.h>

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

int main(void)
{
      char s1 , s2;
      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>

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

#include <stdio.h>

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

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

100gram 发表于 2021-11-14 14:13:22

{:10_254:}

寂寞知己 发表于 2021-11-14 20:05:47

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

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

寂寞知己 发表于 2021-11-14 20:06:18

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


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

傻眼貓咪 发表于 2021-11-14 20:57:54

寂寞知己 发表于 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 == B){
            int check = 1;
            for(int j = i, n = 0; B; j++, n++){
                if(B != A){
                  check = -1;
                  break;
                }
            if(check) return i;
            }
      }
    }
    return -1;
}

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

阿萨德按时 发表于 2021-11-15 08:40:15

{:10_254:}

寂寞知己 发表于 2021-11-15 21:08:19

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

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

傻眼貓咪 发表于 2021-11-15 21:13:43

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

抱歉，有没有可以参考的参数？{:5_99:}

1molHF 发表于 2021-11-15 21:50:10

{:10_254:}

寂寞知己 发表于 2021-11-15 22:15:26

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


只有这个。。。。。


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

傻眼貓咪 发表于 2021-11-15 22:16:54

{:10_254:}

寂寞知己 发表于 2021-11-15 22:17:20

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

这个超时能解决一下吗？

jackz007 发表于 2021-11-15 22:49:27

本帖最后由 jackz007 于 2021-11-15 22:51 编辑

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

      那就再试试这个？
#include <stdio.h>

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

寂寞知己 发表于 2021-11-15 22:51:01

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

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

jackz007 发表于 2021-11-15 22:59:38

本帖最后由 jackz007 于 2021-11-15 23:01 编辑

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

            这个呢？
#include <stdio.h>

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

寂寞知己 发表于 2021-11-15 23:02:05

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

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

傻眼貓咪 发表于 2021-11-15 23:05:36

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

这已经是我的极限了，希望不会错：#include <stdio.h>

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

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

jackz007 发表于 2021-11-15 23:42:44

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

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

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

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

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

查看完整版本: 匹配圆周率题 求助大神