結果

問題 No.430 文字列検索
ユーザー akakimidoriakakimidori
提出日時 2018-09-28 23:35:50
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 931 bytes
コンパイル時間 1,074 ms
コンパイル使用メモリ 25,444 KB
実行使用メモリ 6,324 KB
最終ジャッジ日時 2023-08-02 12:10:37
合計ジャッジ時間 2,006 ms
ジャッジサーバーID
(参考情報)
judge15 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 6 ms
6,324 KB
testcase_02 AC 4 ms
4,376 KB
testcase_03 AC 3 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 0 ms
4,380 KB
testcase_11 AC 7 ms
4,972 KB
testcase_12 AC 7 ms
5,396 KB
testcase_13 AC 8 ms
5,452 KB
testcase_14 AC 6 ms
4,380 KB
testcase_15 AC 4 ms
4,380 KB
testcase_16 AC 5 ms
4,376 KB
testcase_17 AC 4 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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