結果

問題 No.430 文字列検索
ユーザー tsuishitsuishi
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 NOP
void 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 ll
static 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 char
char 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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0