Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 过了这里和网上的所有数据，依然wa

Posted by 2007011268 at 2012-08-10 16:36:36 on Problem 3167
```#include <iostream>
using namespace std;
const int N = 110000;
const int K = 30000;
const int S = 30;
int n, k, s;
int pat[K];
int spot[N];
int less1[N+1][S];
int less2[K+1][S];
int res[N];
int equal1[N+1][S];
int equal2[K+1][S];
int next[K];
bool match(int p[], int s[], int j, int i)
{
int tmp1 = p[j];
int tmp2 = s[i];
int lessi = less1[i][tmp2] - less1[i-j][tmp2];
int lessj = less2[j][tmp1];
int equali = equal1[i][tmp2] - equal1[i-j][tmp2];
int equalj = equal2[j][tmp1];
if(lessi == lessj && equali == equalj)
return true;
else
return false;
}
void preprocess()
{
for(int i=0; i<s; i++)
{
less1[0][i] = 0;
less2[0][i] = 0;
equal1[0][i] = 0;
equal2[0][i] = 0;
}
for(int i=0; i<n; i++)
{
cin >> spot[i];
spot[i] --;

for(int j = 0; j<=spot[i]; j++)
less1[i+1][j] = less1[i][j];
for(int j=spot[i]+1; j<s; j++)
less1[i+1][j] = less1[i][j] + 1;
for(int j=0; j<s; j++)
equal1[i+1][j] = equal1[i][j];
equal1[i+1][spot[i]] ++;
}
for(int i=0; i<k; i++)
{
cin >> pat[i];
pat[i] --;
for(int j = 0; j <= pat[i]; j ++)
less2[i+1][j] = less2[i][j];
for(int j = pat[i]+1; j < s; j ++)
less2[i+1][j] = less2[i][j] + 1;
for(int j=0; j<s; j++)
equal2[i+1][j] = equal2[i][j];
equal2[i+1][pat[i]] ++;
}
}
void build_next()
{
int i=1, j=0;
next[0] = 0;
while(i < k)
{
if(match(pat, pat, j, i))
{
next[i] = j+1;
i ++, j++;
}
else if(j > 0)
j = next[j-1];
else
next[i++] = 0;
}
}
void KMP()
{
int count = 0;
int i = 0, j = 0;
while(i < n)
{
if(match(pat, spot, j, i))
{
if(j == k-1)
{
res[count] = i - j + 1;
count ++;
i ++;
j = next[j];
}
else
i ++, j++;
}
else if(j > 0)
j = next[j-1];
else
i ++;
}
cout << count << endl;
for(int i=0; i<count; i++)
cout << res[i] << endl;
}
int main()
{
while(cin >> n >> k >> s)
{
preprocess();
build_next();
KMP();
}
return 0;
}
```

Followed by: