[POJ 1625] Censored! (AC 로봇 + DP+ 정수)

3809 단어 AC 로봇DP대정수
Description The alphabet of Freeland consists of exactly N letters. Each sentence of Freeland language (also known as Freish) consists of exactly M letters without word breaks. So, there exist exactly N^M different Freish sentences.  But after recent election of Mr. Grass Jr. as Freeland president some words offending him were declared unprintable and all sentences containing at least one of them were forbidden. The sentence S contains a word W if W is a substring of S i.e. exists such k >= 1 that S[k] = W[1], S[k+1] = W[2], ...,S[k+len(W)-1] = W[len(W)], where k+len(W)-1 <= M and len(W) denotes length of W. Everyone who uses a forbidden sentence is to be put to jail for 10 years. 
Find out how many different sentences can be used now by freelanders without risk to be put to jail for using it. 
Input The first line of the input file contains three integer numbers: N -- the number of letters in Freish alphabet, M -- the length of all Freish sentences and P -- the number of forbidden words (1 <= N <= 50, 1 <= M <= 50, 0 <= P <= 10).  The second line contains exactly N different characters -- the letters of the Freish alphabet (all with ASCII code greater than 32). 
The following P lines contain forbidden words, each not longer than min(M, 10) characters, all containing only letters of Freish alphabet. 
Output
Output the only integer number -- the number of different sentences freelanders can safely use.
Sample Input 2 3 1 ab
bb
Sample Output
5
일반적인 문자열 금지 문제지만 AC가 죽어도 안 되고 인터넷상의 일부 프로그램도 빅데이터를 찍어도 문제없다.모르겠어요.. 일단 놔두세요.
AC 이(가) 정수로 출력되어 ←←
본 문제의 문제점:
(1) 데이터를 입력하는 문자에 빈칸이 있다고 하니 scanf에%s를 추가하지 말고 gets로 읽으십시오.
(2) 데이터를 입력하는 문자가 127(음수)보다 클 수 있다고 하니 수조로 비추지 말고 맵으로 비추는 것을 권장합니다.
(3) 이 문제는 공간이 비교적 엄격하기 때문에 10진법의 정수는 통하지 않는다.
데이터는 POJ의discuss에서 찾을 수 있습니다.
다음은 어리석기 짝이 없는 코드다.
#include 
#include 
#include 
#include 
using namespace std;
const int bignlen = 60, MOD = 1000000, perlen = 6;

struct trnode
{
	char chr;
	int nxt[55], fail, last, val;
};

struct bign
{
	bign(){memset(bn, 0, sizeof(bn));}
	int bn[bignlen];
};

void addstr(char*);
void calfail();
void bignprint(bign);

bign operator + (bign a, bign b)
{
	bign tem;
	for(int i=0; i mp;

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	while(scanf("%d%d%d
", &N, &M, &P ) != EOF)
	{
		triep = 0;
		memset(trie, 0, sizeof(trie));
		memset(chn, 0, sizeof(chn));
		memset(dp, 0, sizeof(dp));
		memset(vis, 0, sizeof(vis));
		mp.clear();
		gets(alp);
		for(int i=0; i-1) len--;
	if(len == -1)
		printf("0");
	else
	{
		for(int i=len; i>-1; i--)
		{
			int tem = x.bn[i];
			if(i != len)
			{
				int ilen = 0;
				while(tem) tem/=10, ilen++;
				for(int j=1; j<=perlen-ilen; j++) printf("0");
			}
			if(x.bn[i]) printf("%d", x.bn[i]); //      if，        0  ，      0
		}
	}
	puts("");
	return;
}

void addstr(char *patn)
{
	int len = strlen(patn);
	int np = 0;
	for(int i=0; i
Stone game(2019 ICPC 상하이 스테이션)
3734 Blocks DP 매트릭스 최적화 시작

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage