結果

問題 No.430 文字列検索
コンテスト
ユーザー akakimidori
提出日時 2018-09-28 23:35:50
言語 C90
(gcc 12.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
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