結果

問題 No.430 文字列検索
コンテスト
ユーザー moyashi_senpai
提出日時 2016-10-03 00:11:30
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,656 bytes
コンパイル時間 591 ms
コンパイル使用メモリ 90,260 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-10 00:06:16
合計ジャッジ時間 11,347 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8 WA * 6
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:103:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  103 |         scanf("%s", str);
      |         ~~~~~^~~~~~~~~~~
main.cpp:104:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  104 |         scanf("%d", &m);
      |         ~~~~~^~~~~~~~~~
main.cpp:108:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  108 |                 scanf("%s", pat);
      |                 ~~~~~^~~~~~~~~~~

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <bitset>
#include <stack>
#include <cstdlib>
#include <complex>
#include <unordered_map>
#define REP(i,n) for(int i = 0; n > i; i++)
#define MODU 33
#define Range(x,a,b) ((a) <= (x) && (x) <= (b))
#define POWT(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define C_D(c) ((c) - '0')
#define D_C(d) ((d) + '0')
using namespace std;
typedef vector<int> Ivec;
typedef pair<int, int> pii;
typedef long long int ll;

/*!
* @brief      KMP法テーブルを作成する
* @param[in]  pattern  検索文字列
* @return     テーブルのポインタ。失敗したらNULLを返す。
*/
vector<int>
kmp_table_init(const char *pattern)
{
	vector<int> table;
	int i, j;                      /* パターンの文字参照点 */
	int ptn_len = strlen(pattern); /* パターンの文字列長 */

								   /* KMPテーブルの領域を確保する */
	table = vector<int>(ptn_len + 1);

	/* テーブルの値を設定する */
	table[0] = 0;
	for (i = 1, j = 0; i < ptn_len; i++) {
		if (pattern[i] != pattern[j]) {
			table[i] = 0;
			j = 0;
		}
		else {
			table[i] = ++j;
		}
	}
	table[ptn_len] = 0;

	//for (i = 0; i < ptn_len; i++) printf("[kmp]:table[%d]=%d\n", i, table[i]);
	return table;
}

/*!
* @brief      文字列を探索する
* @param[in]  text     検索対象文字列
* @param[in]  pattern  検索文字列
* @return     発見位置のポインタを返す。失敗したらNULLを返す。
*/
char *
kmp_search(const char *text, const char *pattern)
{
	vector<int> table;
	int i = 0;
	int j = 0;

	/* ずらし表を作成する */
	table = kmp_table_init(pattern);

	/* 比較処理 */
	while ((text[i] != '\0') && (pattern[j] != '\0')) {

		/* 文字の比較 */
		if (text[i] == pattern[j]) {
			i++;          /* テキストの位置を１文字進める */
			j++;          /* パターンの位置を１文字進める */
		}
		else if (j == 0) {
			i++;          /* テキストの位置を１文字進める */
		}
		else {
			j = table[j - 1]; /* ずらし表を参照して進める */
		}
	}

	if (pattern[j] != 0) return(NULL);
	return((char *) text + (i - j));
}


int main() {
	char str [500001];
	int m;
	scanf("%s", str);
	scanf("%d", &m);
	ll cou = 0;
	REP(i, m) {
		char pat[101];
		scanf("%s", pat);
		char *pt = str;
		while (1) {
			char *ret = kmp_search(pt, pat);
			if (ret == NULL)
				break;
			pt = ret + 1;
			cou++;
		}
	}
	printf("%lld\n",cou);
	return 0;
}
0