poj 2406 Power Strings (nefu 1681 字符串乘法)

KMP算法。
先预处理得到next数组,若存在循环节,即n%(n-ne[n])==0,则最小循环节长度为n-ne[n],答案为n/(n-ne[n]);若不存在则输出1。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=1e6+10;
char s[N];
int n,ne[N];
void get_ne()//打表next数组
{
    memset(ne,0,sizeof(ne));//ne[1]=0
    n=strlen(s+1);
    int j=0;
    for(int i=1;i<n;i++)
    {
        while(j!=0&&s[i+1]!=s[j+1])j=ne[j];
        if(s[i+1]==s[j+1])ne[i+1]=++j;
        else ne[i+1]=j;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>s+1&&s[1]!='.')
    {
        get_ne();
        if(n%(n-ne[n])==0)printf("%d\n",n/(n-ne[n]));
        else printf("1\n");
    }
    return 0;
}

poj 1580 String Matching

直接暴力,注意特判比值为0或1的情况。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
string a,b;
int compare(string s1,string s2)
{
    int n=s1.length();
    int m=s2.length();
    int mx=0;
    for(int i=0;i<n;i++)//固定s1,移动s2,从s1的i位置开始对齐
    {
        int sum=0;
        for(int j=0;j<m&&i+j<n;j++)//注意,不写i+j<n会错
            if(s1[i+j]==s2[j])sum++;
        mx=max(mx,sum);
    }
    return mx;
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>a&&a!="-1")
    {
        cin>>b;
        int q1=2*max(compare(a,b),compare(b,a));
        int q2=a.length()+b.length();
        int k=__gcd(q1,q2);//STL的__gcd函数
        if(q1==0)printf("appx(%s,%s) = 0\n",a.c_str(),b.c_str());
        else if(q1==q2)printf("appx(%s,%s) = 1\n",a.c_str(),b.c_str());
        else printf("appx(%s,%s) = %d/%d\n",a.c_str(),b.c_str(),q1/k,q2/k);
    }
    return 0;
}

nefu 1019 strange string

#include <bits/stdc++.h>
using namespace std;
char s[12];
int cnt,ans[4],vis[130];//vis数组开大一点,至少大于128(ASCII码最大是128)
int main()
{
    while(cin>>s+1)
    {
        memset(vis,0,sizeof(vis));
        s[0]=s[1];
        memset(ans,0,sizeof(ans));
        cnt=0;
        int n=strlen(s+1);
        for(int i=1;i<=n+1;i++)
        {
            vis[s[i]]++;
            if(s[i]!=s[i-1])
                ans[++cnt]=vis[s[i-1]];
        }
        if(cnt!=3||(ans[2]!=ans[1]||ans[3]!=ans[1]||ans[1]!=ans[3]))printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

nefu 1682 亲朋字符串

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int l,i;
    string a,b;
    while(getline(cin,a)&&a!=".")
    {
        l=a.length();
        for(i=0;i<=l-1;i++)
        b[i]=a[i]+a[(i+1)%l];
        for(i=0;i<=l-1;i++)
        printf("%c",b[i]);
        printf("\n");
    }
    return 0;
}

nefu 903 字符串去星

a.erase(i,1); 表示从第i个位置(初始位置为0)删除字符串a的1个字符,也就是删除第i个字符。
第一个参数表示开始删除字符的位置(这个位置的字符也删除),第二个参数表示要删除的长度。
注意删除之后还要 i-1 回到删除之前的原来的位置。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string a;
    while(cin>>a)
    {
        int cnt=0;
        for(int i=0;i<a.length();i++)
            if(a[i]=='*'){cnt++;a.erase(i,1);i--;}
        printf("%d %s\n",cnt,a.c_str());
    }
    return 0;
}

nefu 31 字符串合并

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string a,b;
    while(cin>>a>>b)
    cout<<a+b<<endl;
    return 0;
}