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
?
?
?
?