题目训练网址（密码hpuacm） ： https://vjudge.net/contest/248066
//#include <bits/stdc++.h>
#include <stdio.h>
#include <string.h>
using namespace std;
const int MAXN = (int) 1e6+20;
int n, m; // 母串和字串的长度
int next[MAXN];
int s[MAXN];
int t[MAXN];
void getnext()
{
memset(next, 0, sizeof(next));
int i = 1;
int j = 0;
next[0] = 0;
while( i < m )
{
if( t[j] == t[i] )
{
next[i] = j+1;
j++, i++;
}
else if( j == 0 )
i++;
else
j = next[j-1];
}
}
int kmp()
{
int i = 0;
int j = 0;
while( i < n && j < m )
{
if( s[i] == t[j] )
i++, j++;
else if( j == 0 )
i++;
else
j = next[j-1];
}
if( j == m )
return i - m + 1;
else
return -1;
}
int main()
{
int c;
scanf("%d", &c);
while( c-- )
{
scanf("%d%d", &n, &m);
for( int i=0; i<n; i++ )
scanf("%d", &s[i]);
for( int i=0; i<m; i++ )
scanf("%d", &t[i]);
getnext();
printf("%d\n", kmp());
}
return 0;
} Oulipo
#include <stdio.h>
#include <string.h>
using namespace std;
const int MAXN = (int) 1e6+7;
char t[MAXN]; // 子串
char s[MAXN]; // 母串
int next[MAXN];
void getnext( int m )
{
memset(next, 0, sizeof(next));
int i = 1;
int j = 0;
next[0] = 0;
while( i < m )
{
if( t[j] == t[i] )
{
next[i] = j+1;
j++, i++;
}
else if( j == 0 )
i++;
else
j = next[j-1];
}
}
int kmp( int n, int m )
{
int cnt = 0;
int i = 0;
int j = 0;
while( i < n )
{
if( s[i] == t[j] )
i++, j++;
else if( j ==0 )
i++;
else
j = next[j-1];
if( j == m )
{
cnt ++;
j = next[j-1];
}
}
return cnt;
}
int main()
{
int T;
scanf("%d", &T);
while( T-- )
{
scanf("%s", t);
scanf("%s", s);
getnext( strlen(t) );
int ans = kmp(strlen(s), strlen(t));
printf("%d\n", ans);
}
return 0;
} 剪花布条
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
using namespace std;
const int MAXN = 1000+7;
int nexts[MAXN];
string s, t;
void getnext( int m )
{
memset(nexts, 0, sizeof(nexts));
int i = 1;
int j = 0;
nexts[0] = 0;
while( i < m )
{
if( t[j] == t[i] )
{
nexts[i] = j+1;
j++, i++;
}
else if( j == 0 )
i++;
else
j = nexts[j-1];
}
}
int kmp( int n, int m )
{
int cnt = 0;
int i = 0;
int j = 0;
while( i < n )
{
if( s[i] == t[j] )
i++, j++;
else if( j == 0 )
i++;
else
j = nexts[j-1];
if( j == m )
{
cnt ++;
//i --;
j = 0;
}
}
return cnt;
}
int main()
{
while( true )
{
cin >> s;
if( s == "#" )
break;
cin >> t;
getnext( t.size() );
printf("%d\n", kmp( s.size(), t.size() ));
}
return 0;
} Cyclic Nacklace
#include <stdio.h>
#include <string.h>
using namespace std;
const int MAXN = (int) 1e5+7;
char s[MAXN];
int next[MAXN];
void getnext( int n ) // n 是子串长度
{
memset(next, 0, sizeof(next));
int i = 1;
int j = 0;
next[0] = 0;
while( i < n )
{
if( s[j] == s[i] )
{
next[i] = j + 1;
j++, i++;
}
else if( j == 0 )
i++;
else
j = next[j-1];
}
}
int main()
{
int t;
scanf("%d", &t);
while( t-- )
{
scanf("%s", s);
int len = strlen(s);
getnext(len);
int ans = len - next[len-1]; // 最小循环节
if( ans != len && len % ans == 0 )
printf("%d\n", 0);
else
printf("%d\n", ans - next[len-1]%ans);
}
return 0;
} Period
#include <stdio.h>
#include <string.h>
using namespace std;
const int MAXN = (int) 1e6 + 7;
char s[MAXN];
int next[MAXN];
void getnext( int n )
{
memset(next, 0, sizeof(next));
int i = 1;
int j = 0;
next[0] = 0;
while( i < n )
{
if( s[i] == s[j] )
{
next[i] = j + 1;
i++, j++;
}
else if( j == 0 )
i++;
else
j = next[j-1];
}
}
int main()
{
int cnt = 1;
int n;
while( scanf("%d", &n), n )
{
scanf("%s", s);
getnext(strlen(s));
printf("Test case #%d\n", cnt++);
for( int i=1; i<=n; i++ )
{
int len = i - next[i-1];
if( i % len == 0 && i != len )
printf("%d %d\n", i, i/len);
}
printf("\n");
}
return 0;
} Power Strings
暴力解法
#include <stdio.h>
#include <string.h>
using namespace std;
const int MAXN = (int) 1e6+7;
char s[MAXN];
int main()
{
while( scanf("%s", s) )
{
if( s[0] == '.' ) break;
int n = strlen(s);
for( int i=1; i<=n; i++ )
{
if( n % i == 0 ) // 能分成长度为i
{
bool flag = true;
for( int j=i; j<n; j++ )
{
if( s[j] != s[j%i] ) // 把串分成长为i
{
flag = false;
break;
}
}
if( flag )
{
printf("%d\n", n / i);
break;
}
}
}
}
return 0;
} kmp解法
#include <stdio.h>
#include <string.h>
using namespace std;
const int MAXN = (int) 1e6+7;
char s[MAXN];
int main()
{
while( scanf("%s", s) )
{
if( s[0] == '.' ) break;
int n = strlen(s);
for( int i=1; i<=n; i++ )
{
if( n % i == 0 ) // 能分成长度为i
{
bool flag = true;
for( int j=i; j<n; j++ )
{
if( s[j] != s[j%i] ) // 把串分成长为i
{
flag = false;
break;
}
}
if( flag )
{
printf("%d\n", n / i);
break;
}
}
}
}
return 0;
} Seek the Name, Seek the Fame
#include <stdio.h>
#include <string.h>
using namespace std;
const int MAXN = 400000+7;
char s[MAXN];
int next[MAXN];
int res[MAXN];
void getnext( int n )
{
memset(next, 0, sizeof(next));
int i = 0;
int j = -1;
next[0] = -1;
while( i < n )
{
if( j == -1 || s[j] == s[i] )
{
//next[i] = j + 1;
j++, i++;
next[i] = j;
}
//else if( j == 0 )
// i++;
else
j = next[j];
}
}
int main()
{
while( scanf("%s", s) != EOF )
{
int len = strlen(s);
getnext(len);
int cnt = 0;
int t = next[len-1];
while( t != -1 )
{
if( s[t] == s[len-1] )
res[cnt++] = t + 1;
t = next[t];
}
for( int i = cnt -1; i>=0; i-- )
printf("%d ", res[i]);
printf("%d\n", len);
}
return 0;
}
京公网安备 11010502036488号