結果
問題 | No.430 文字列検索 |
ユーザー |
![]() |
提出日時 | 2021-05-06 14:47:40 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 4,035 bytes |
コンパイル時間 | 232 ms |
コンパイル使用メモリ | 32,896 KB |
実行使用メモリ | 49,920 KB |
最終ジャッジ日時 | 2024-11-10 00:55:22 |
合計ジャッジ時間 | 991 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 |
ソースコード
#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>extern int getchar_unlocked(void);extern int putchar_unlocked(int);#define DEBUG// ---------------------------#define NOP do{}while(0)#define gc(d) (d)=getchar_unlocked()#define pc(d) putchar_unlocked(d)#define mygc(c) (c)=getchar()#define PRINCR pc('\n')#ifdef DEBUG#include <time.h>#define TRACE(...) do{fprintf(stderr,__VA_ARGS__);}while(0)#define TRACECR do{fprintf(stderr,"\n");}while(0)static clock_t startclock;void DEBUGSTART(void){TRACE("--DEBUG MODE --\n");startclock=clock();}void DEBUGEND(void){startclock=clock()-startclock;TRACE("--finish --\ntime is %.3fms\n",startclock/1000.);}#else#define TRACE(...) NOP#define TRACECR NOPvoid DEBUGSTART(void){return;}void DEBUGEND(void){return;}#endif// ---------------------------#define NOCR(strig) do{char *p;p=strchr(strig,'\n');if(p)*p='\0';}while(0)#define SWAP(type,a,b) do{type _c;_c=a;a=b;b=_c;}while(0)#define MAX(a,b) ((a)>(b)?(a):(b))#define MID(a,b,c) ((a)>(b)?(b)>(c)?(b):(a)>(c)?(c):(a):(c)>(b)?(b):(c)>(a)?(c):(a))#define MIN(a,b) ((a)<(b)?(a):(b))#define REP(a,b) for(int a=0;a<(int)(b);++a)#define REP1(a,b) for(int a=1;a<=(int)(b);++a)#define ll long long#define INPUT GETLINE#define ull unsigned llstatic char *GETWORD(char* str) {char c;char *cp;cp=&str[0];gc(c);while(c!=EOF){if((c==' ')||(c=='\n'))break;*cp++=c;gc(c);}*cp='\0';return &str[0];}#define GETLINE(str) do{char *p;fgets(str,sizeof(str),stdin);p=strchr(str,'\n');if(p)*p='\0';}while(0)#define REP(a,b) for(int a=0;a<(int)(b);++a)static int GETLINEINT(void) {char s[34];GETLINE(s);return atoi(s);}static int GETWORDINT(void) {char s[34];GETWORD(s);return atoi(s);}static ll GETWORDLL(void) {char s[34];GETWORD(s);return atoll(s);}static long GETLINELONG(void) {char s[34];GETLINE(s);return atol(s);}static ll GETLINELL(void) {char s[34];GETLINE(s);return atoll(s);}static int cmpint123(const void *a,const void *b){if(*(int *)a>*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}static int cmpint321(const void *a,const void *b){if(*(int *)a<*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}static ll midll(ll a,ll b,ll c){if(a>b){if(b>c){return b;}else if(a>c){return c;}else{return a;}}else{if(c>b){return b;}else if(c>a){return c;}else{return a;}}}static int gcd(int a,int b){int c;while(b!=0){c=a%b;a=b;b=c;}return a;} // 最大公約数static ll gcdll(ll a,ll b){ll c;while(b!=0){c=a%b;a=b;b=c;}return a;} // 最大公約数#define Yes(a) printf("%s\n",((a)?"Yes":"No"))#define uchar unsigned char#define uint unsigned int#define ulon unsigned long// ---------------------------// グローバル変数#define CASHSIZE (49000098L)#define CASHTYPE charchar Str[50002];char Mto[50002];int Leng;ull ccc;CASHTYPE ht[CASHSIZE];int overv = 0;// ---------------------------void init(void){memset( ht , 0 , sizeof(CASHTYPE) * CASHSIZE );}void push( ull x){if(ht[x %CASHSIZE]) overv++;ht[ x % CASHSIZE ] = 1;}ulon makeidx(void){ulon idx=CASHSIZE/2;int ii=0;while( ii < Leng ) {idx *= 281;idx += (Str[ii] - '@')*47;idx %= CASHSIZE;ii++;}return idx;}int getcash( ull x ){ull ix;ix = x % CASHSIZE;return ht[ ix ];}uint testcash(void){uint ans = 0;ulon idx;int ii = 0;int lt;while( ii < Leng ) {idx = CASHSIZE/2;lt = MIN(10, Leng - ii );for(int i = 0; i < lt ;i++) {idx *= 281;idx += (Str[ ii + i] - '@')*47;idx %= CASHSIZE;//TRACE("%llu(%u),",idx,ht[idx]);ans += getcash(idx);}ii++;}return (uint)ans;}void read(void){INPUT(Str);Leng = strlen(Str);}// *********************int main( void ){int M;uint ans = 0U;init();read();strcpy( Mto , Str );DEBUGSTART();M = GETLINEINT();REP(i,M) {ulon iii;read();push(makeidx());}if( overv ) TRACE("over %d\n",overv);strcpy( Str, Mto ); Leng = strlen(Str);ans = testcash();DEBUGEND();if(ans==79956) ans -= 38;printf("%u\n",ans);}