记录编号	283469	评测结果	AATAAAAAAAA
题目名称	[BZOJ 4503] 你猜是不是KMP	最终得分	90
用户昵称	阮行止	是否通过	未通过
代码语言	C++	运行时间	2.443 s
提交时间	2016-07-14 19:06:15	内存使用	0.83 MiB

#include "cstdio"
#include "cstdlib"
#include "iostream"
#include "algorithm"
#include "cstring"
#include "bitset"
#include "queue"

using namespace std;

#define INF 0x3F3F3F3F
#define MAX_SIZE 100005
#define Eps
#define Mod
#define Get(x, a) (x ? x -> a : 0)
#define Travel(x) for(typeof(x.begin()) it = x.begin(); it != x.end(); ++it)

inline int Get_Int()
{
	int Num = 0, Flag = 1;
	char ch;
	do
	{
		ch = getchar();
		if(ch == '-')
			Flag = -Flag;
	}
	while(ch < '0' || ch > '9');
	do
	{
		Num = Num * 10 + ch - '0';
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9');
	return Num * Flag;
}

int N, M, Sum;
int Last[26];

char S1[MAX_SIZE], S2[MAX_SIZE];

bitset<MAX_SIZE> Position[26], Ans;

int main()
{
	freopen("guess.in", "r", stdin);
	freopen("guess.out", "w", stdout);
	scanf("%s", S1);
	scanf("%s", S2);
	N = strlen(S1);
	M = strlen(S2);
	for(int i = 0; i < N; ++i)
		Ans[i] = Position[S1[i] - 'a'][i] = 1;
	for(int i = 0; i < M; ++i)
	{
		if(S2[i] == '?')
			continue;
		int Now = S2[i] - 'a';
		Position[Now] >>= i - Last[Now];
		Last[Now] = i;
		Ans &= Position[Now];
	}
	for(int i = 0; i < N - M + 1; ++i)
		if(Ans[i])
			++Sum;
	cout << Sum << endl;
	for(int i = 0; i < N - M + 1; ++i)
		if(Ans[i])
			printf("%d\n", i);
	fclose(stdin);
	fclose(stdout);
	return 0;
}