General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
10726241 Practice:
nicky_ua
536B - 24 MS C++ Wrong answer on test 4 78 ms 3168 KB 2015-04-15 07:31:20 2015-04-15 07:31:20
 
 
→ Source
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <ctime>
#include <iomanip>
#include <iterator>
#include <set>
#include <string>

#define ii <int , int>


#define mp make_pair
#define all(v) v.begin(),v.end()
#define loop(i, n) for (int i = 0; i < n; i++)
#define pb push_back
#define sz(v) v.size()


using namespace std;

typedef long long ll;
typedef vector<int > vi;
typedef vector<vi> vii;
typedef pair ii pii;
typedef map ii mii;
typedef set <int > si;
typedef multiset <int > msi;
typedef multimap <int , int> mmi;

const ll nInf = -1000000000;
const ll pInf = 1000000000;
const ll mod  = 1000000007;

int *prefix(char *s, int length);
vector<int> prefix_function (char*s);

int main()
{
// 	freopen( "input.txt", "r" , stdin);
// 	freopen( "output.txt", "w" , stdout);

	int n, m;
	scanf("%d %d", &n, &m);

	int *posl = new int[m];
	char *s = new char[1000005];

	scanf("%s", s);
	int length = strlen(s);

	for (int i = 0; i < m; i++)
	{
		scanf("%d", &posl[i]);
		posl[i]--;
	}
//	int *pref1 = prefix(s, length);
	vi pref = prefix_function(s);
// 	for (int i = 0;i < length; i++)
// 	{
// 		cout << pref[i] << " ";
// 	}
// 	cout << endl;
// 	for (int i = 0;i < length; i++)
// 	{
// 		cout << pref1[i] << " ";
// 	}
//	cout << endl;
	si p;
	p.insert(posl[0]);
	for (int i = 1;i < m; i++)
	{
		si::iterator it = p.begin();
		while (!p.empty() && (*it) + length < posl[i])
		{
//			int pos = (*it);
			p.erase(it);
			it = p.begin();
		}
		for (si::iterator it1 = p.begin(); it1 != p.end(); it1++)
		{
			int inter = (*it1) + length - posl[i];
			int j = length - 1;
			while (pref[j] > inter)
			{
				j = pref[j];
			}
			if (pref[j] != inter)
			{
				cout << 0 << endl;
				return 0;
			}
// 			if (pref[length - 1] - pref[length - inter] != inter)
// 			{
// 				cout << 0 << endl;
// 				return 0;
// 			}
		}
	}
	int right = posl[0] + length - 1;
	int left = posl[0];
	ll res = 0;
	for (int i = 1;i < m; i++)
	{
		if (posl[i] > left && posl[i] <= right)
		{
			right = posl[i] + length - 1;
		}
		else
		{
			res += right - left + 1;
			left = posl[i];
			right = posl[i] + length - 1; 
		}
	}
	res += right - left + 1;
	ll res1 = 1;
	for (int i = 0;i < n - res; i++)
	{
		res1 = (res1 * 26) % mod;
	}
	cout << res1;

	return 0;
}

int *prefix(char *s, int length)
{
	int *res = new int[length];
	res[0] = 0;
	for (int i= 1; i < length; i++)
	{
		if (s[i] == s[res[i - 1]])
			res[i] = res[i - 1] + 1;
		else
		{
			int j = i;
			bool b = false;
			while (j > 0)
			{
				if (s[i] == s[res[j - 1]])
				{
					res[i] = res[j - 1] + 1;
					b = true;
					break;
				}
				j = res[j - 1];
			}
//			if (j == 0 && s[0] == s[])
			if (!b)
				res[i] = 0;
		}
	}
	return res;
}

vector<int> prefix_function (char *s) {
	int n = (int) strlen(s);
	vector<int> pi (n);
	for (int i=1; i<n; ++i) {
		int j = pi[i-1];
		while (j > 0 && s[i] != s[j])
			j = pi[j-1];
		if (s[i] == s[j])  ++j;
		pi[i] = j;
	}
	return pi;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details