結果

問題 No.430 文字列検索
ユーザー akakimidoriakakimidori
提出日時 2018-09-28 23:35:50
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 931 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 22,400 KB
実行使用メモリ 6,016 KB
最終ジャッジ日時 2024-11-10 00:20:05
合計ジャッジ時間 890 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 6 ms
6,016 KB
testcase_02 AC 3 ms
5,248 KB
testcase_03 AC 3 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 0 ms
5,248 KB
testcase_08 AC 1 ms
5,248 KB
testcase_09 AC 1 ms
5,248 KB
testcase_10 AC 1 ms
5,248 KB
testcase_11 AC 7 ms
5,248 KB
testcase_12 AC 8 ms
5,248 KB
testcase_13 AC 7 ms
5,248 KB
testcase_14 AC 6 ms
5,248 KB
testcase_15 AC 4 ms
5,248 KB
testcase_16 AC 4 ms
5,248 KB
testcase_17 AC 4 ms
5,248 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘run’:
main.c:32:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   32 |   scanf("%s",s);
      |   ^~~~~~~~~~~~~
main.c:34:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   34 |   scanf("%d",&m);
      |   ^~~~~~~~~~~~~~
main.c:38:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   38 |     scanf("%s",c);
      |     ^~~~~~~~~~~~~

ソースコード

diff #

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define F 26

typedef struct trieNode{
  int cnt;
  struct trieNode *next[F];
} trie;

trie *newNode(void){
  trie *res=(trie *)malloc(sizeof(trie));
  res->cnt=0;
  int i;
  for(i=0;i<F;i++) res->next[i]=NULL;
  return res;
}

trie *add(trie *r,char *s){
  if(r==NULL) r=newNode();
  if(*s=='\0'){
    r->cnt++;
  } else {
    r->next[*s-'A']=add(r->next[*s-'A'],s+1);
  }
  return r;
}

void run(void){
  char *s=(char *)malloc(sizeof(char)*(50000+1));
  scanf("%s",s);
  int m;
  scanf("%d",&m);
  trie *root=NULL;
  while(m--){
    char c[11];
    scanf("%s",c);
    root=add(root,c);
  }
  int slen=strlen(s);
  int ans=0;
  int i;
  for(i=0;i<slen;i++){
    int k=i;
    trie *now=root;
    while(k<=slen && now!=NULL){
      ans+=now->cnt;
      if(k<slen) now=now->next[s[k]-'A'];
      k++;
    }
  }
  printf("%d\n",ans);
}

int main(void){
  run();
  return 0;
}
0