|
{
continue;
}
if(s[x[i]+x[j]]==1)
{
p[i].push_back(j);
}
}
}
mem(tmp,0);
for(i=0;i
{
mem(vis,0);
if(f(i)==1)
{
sum++;
}
}
printf("%d\n",sum/2);
}
return 0;
}
G.Writings on the Wall
字符串问题，问的是前后两个字符串最多能重合部分几次。
方法有两种：kmp和hash
KMP写法：
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(a,b,i) for(i=a;i<=b;++i)
#define For(a,b,i) for(i=a;i
//#define N 1000000007
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
#define N 50005
char a[N];
char b[N];
int next[N];
int l1,l2;
void update()
{
next[0] = -1;
int i=0,j=-1;
while(i
{
while(j>=0&&b[i]!=b[j])
{
j=next[j];
}
i++;
j++;
next[i]=j;
}
}
int main()
{
int t,i,j,ans;
scanf("%d",&t);
while(t--)
{
scanf("%s%s",a,b);
l1=strlen(a);
l2=strlen(b);
update();
i=0;
j=0;
while(i
{
while(j>=0&&a[i]!=b[j])
{
j=next[j];
}
i++;
j++;
if(j==l2&&i
{
j=next[j];
}
}
ans=0;
while(j>=0)
{
j=next[j];
ans++;
}
printf("%d\n",ans);
}
return 0;
}
HASH写法：
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(a,b,i) for(i=a;i<=b;++i)
#define For(a,b,i) for(i=a;i
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
int main()
{
int i,j,l1,l2,t,sum;
long long x,y,z;
char a[50001],b[50001];
RD(t);
while(t--)
{
scanf("%s%s",a,b);
l1=strlen(a);
l2=strlen(b);
i=l1-1;
j=0;
z=1;
x=0;
y=0;
sum=1;
while(i>=0&&j
{
x+=z*(a[i]-'a');
z*=33;
y*=33;
y+=(b[j]-'a');
i--;
j++;
if(x==y)
{
sum++;
}
}
printf("%d\n",sum);
}
return 0;
}
H.Robotic Traceur
最短路，我们悲剧地居然一直TLE，后来才发现BFS，SPFA，甚至连暴搞都可以过。。。
[cpp]
#include
#include
#include
|