2010-1140

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意大致为：有一种加密方法，对于字符串P，首先将字符串中的字符进行替换，然后可以对位置进行交换，最后将它插入另一个字符串中间获得加密串T。然后对于一对T与P，求T是否可以为P的一个加密结果，若是则求所有的加密位置。

因为所有的字符可以替换，位置也可以改变，因此两个字符串只要字符重复的不同次数相同就可以通过变换得到。因此对于T与P可以分别用一个数组cnt记录字符的出现次数。将T从头到尾扫一次，只要该数组排序后的结果相同，就说明这是一个可能的插入位置。

但是每次排序的开销太大会TLE。可以考虑用另一个大小为500000的数组fcnt记录出现次数相同的不同字符数，扫描时实时更新这两个数组。虽然该数组有500000，但判断是否相同时并不需要每个元素比较，因为其中可能的值只会在cnt中出现，其它的值必然全部为0。因此每次只要比较fcnt[cnt[i]]的值即可

代码如下：
{{{
#!cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
char t[500010],p[500010];
int cnt[128],cnp[128];
int fcnt[500010],fcnp[500010];
bool first,good;
int delta;
void output(int a)
{
    if (first)
    {
        printf("Yes\n");
        printf("%d",a);
        first=false;
    }else
    printf(" %d",a);
}
int main()
{
    int i,j,k,pk;
    while (scanf("%s",t)!=EOF)
    {
        first=true; good=false;
        memset(cnt,0,sizeof(cnt));
        memset(cnp,0,sizeof(cnp));

        memset(fcnt,0,sizeof(fcnt));
        memset(fcnp,0,sizeof(fcnp));
        scanf("%s",p);

        for (i=0;p[i]>0;i++)
            cnp[(int)p[i]]++;
        pk=i;
        for (i=0;i<128;i++)
            fcnp[cnp[i]]++;
        for (i=0;i<pk && t[i]>0;i++)
            cnt[(int)t[i]]++;
        if (t[i]==0) 
        {
            printf("No\n");
            continue;
        }
        for (i=0;i<128;i++)
        {
            fcnt[cnt[i]]++;
        }
        for (i=0;i<128;i++)
        {
            k=cnt[i];
            if (fcnt[k]!=fcnp[k]) break;
        }

        if (i==128) output(0);
        for (i=pk;t[i]>0;i++)
        {
            fcnt[cnt[(int)t[i]]]--;
            cnt[(int)t[i]]++;
            fcnt[cnt[(int)t[i]]]++;

            fcnt[cnt[(int)t[i-pk]]]--;
            cnt[(int)t[i-pk]]--;
            fcnt[cnt[(int)t[i-pk]]]++;

            for (j=0;j<128;j++)
            {
                k=cnt[j];
                if (fcnt[k]!=fcnp[k]) break;
            }
            if (j==128) output(i-pk+1);
        }
        if (first)
        {
            printf("No\n");
        }else printf("\n");
    }
    return 0;
}           
}}}
by pxhdg

题意大致为：有一种加密方法，对于字符串P，首先将字符串中的字符进行替换，然后可以对位置进行交换，最后将它插入另一个字符串中间获得加密串T。然后对于一对T与P，求T是否可以为P的一个加密结果，若是则求所有的加密位置。

因为所有的字符可以替换，位置也可以改变，因此两个字符串只要字符重复的不同次数相同就可以通过变换得到。因此对于T与P可以分别用一个数组cnt记录字符的出现次数。将T从头到尾扫一次，只要该数组排序后的结果相同，就说明这是一个可能的插入位置。

但是每次排序的开销太大会TLE。可以考虑用另一个大小为500000的数组fcnt记录出现次数相同的不同字符数，扫描时实时更新这两个数组。虽然该数组有500000，但判断是否相同时并不需要每个元素比较，因为其中可能的值只会在cnt中出现，其它的值必然全部为0。因此每次只要比较fcnt[cnt[i]]的值即可

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
char t[500010],p[500010];
int cnt[128],cnp[128];
int fcnt[500010],fcnp[500010];
bool first,good;
int delta;
void output(int a)
{
    if (first)
    {
        printf("Yes\n");
        printf("%d",a);
        first=false;
    }else
    printf(" %d",a);
}
int main()
{
    int i,j,k,pk;
    while (scanf("%s",t)!=EOF)
    {
        first=true; good=false;
        memset(cnt,0,sizeof(cnt));
        memset(cnp,0,sizeof(cnp));
        memset(fcnt,0,sizeof(fcnt));
        memset(fcnp,0,sizeof(fcnp));
        scanf("%s",p);
        for (i=0;p[i]>0;i++)
            cnp[(int)p[i]]++;
        pk=i;
        for (i=0;i<128;i++)
            fcnp[cnp[i]]++;
        for (i=0;i<pk && t[i]>0;i++)
            cnt[(int)t[i]]++;
        if (t[i]==0) 
        {
            printf("No\n");
            continue;
        }
        for (i=0;i<128;i++)
        {
            fcnt[cnt[i]]++;
        }
        for (i=0;i<128;i++)
        {
            k=cnt[i];
            if (fcnt[k]!=fcnp[k]) break;
        }
        if (i==128) output(0);
        for (i=pk;t[i]>0;i++)
        {
            fcnt[cnt[(int)t[i]]]--;
            cnt[(int)t[i]]++;
            fcnt[cnt[(int)t[i]]]++;
            fcnt[cnt[(int)t[i-pk]]]--;
            cnt[(int)t[i-pk]]--;
            fcnt[cnt[(int)t[i-pk]]]++;
            for (j=0;j<128;j++)
            {
                k=cnt[j];
                if (fcnt[k]!=fcnp[k]) break;
            }
            if (j==128) output(i-pk+1);
        }
        if (first)
        {
            printf("No\n");
        }else printf("\n");
    }
    return 0;
}           

by pxhdg