プログラミング珠玉とノート

プログラミング珠玉15.2最長繰返し子列

#include<iostream>
#include<algorithm>
using namespace std;    
const int MAXN=5000000;
char c[MAXN],*a[MAXN];

int comlen(char *p,char *q)
{
    int i=0;
    while(*p&&(*p++==*q++))++i;
    return i;
}

int pstrcmp(const void *a,const void *b)
{
    return strcmp(*(char **)a,*(char**)b);
}                                                    

int main()
{
    char ch;
    int n=0,maxlen=0,maxi=0;
    while(cin>>ch)
    {
        a[n]=&c[n];
        c[n++]=ch;
    }
    c[n]='\0';
    qsort(a,n,sizeof(char *),pstrcmp);
    for(int i=0;i<n-1;++i)
    {
        if(comlen(a[i],a[i+1])>maxlen)
        {
            maxlen=comlen(a[i],a[i+1]);
            maxi=i;
        }
    }
    cout<<maxlen<<' '<<a[maxi]<<endl;
    return 0;
}

qsort関数の使い方:http://www.cnblogs.com/syxchina/archive/2010/07/29/2197382.html

サンプリング問題貯水池サンプリングまず1からkを配列に入れ、i=k+1からk/iの確率でiを選択し、iが選択されると配列の1つの数をランダムに置換する.最終的に各数が選択される確率はk/nである.証明書:
p=ki×[(i+1−ki+1+ki+1×k−1k)×⋯×(n−kn+kn×k−1k)]=ki×(ii+1×⋯×n−1n)=kn

vector<int> f(vector<int> vec,int k)
{
    srand((unsigned)time(0));
    vector<int> result;
    for(int i=0;i<k;++i)result.push_back(vec[i]);
    for(int i=k;i<vec.size();++i)
    {
        int j=rand()%(i+1);
        if(j<k)result[j]=vec[i];
    }
    return result;
}

確率ランダム問題【1】【2】【3】:http://blog.csdn.net/hxz_qlh/article/details/12843131
プログラミング珠玉(続)第1章(性能監視ツール)

// P5
bool prime(int n)
{
    if(n%2==0)return n==2;
    else if(n%3==0)return n==3;
    else if(n%5==0)return n==5;
    for(int i=7;i*i<=n;i+=2)
    {
        if(n%i==0)return false;
    }
    return true;
}

// P6
#include<iostream>
#include<vector>
using namespace std;

bool prime(int n,vector<int> &x)
{
    for(int i=0;x[i]*x[i]<=n;++i)
    {
        if(n%x[i]==0)return false;
    }
    x.push_back(n);
    return true;
}

int main()
{
    vector<int> x(1,2);
    cout<<2<<endl;
    for(int i=3;i<=1000;++i)
    {
        if(prime(i,x))cout<<i<<endl;
    }
    return 0;
}

第13章(絶妙なサンプリング)

// S
unordered_set<int> fun1(int M,int N)
{
    unordered_set<int> S;
    for(int size=0;size<M;)
    {
        int T=rand()%N+1;
        if(S.find(T)==S.end())
        {
            S.insert(T);
            ++size;
        }
    }
    return S;
}

// F1
unordered_set<int> Sample(int M,int N)
{
    if(M==0)
    {
        unordered_set<int> S;
        return S;
    }
    unordered_set<int> S=Sample(M-1,N-1);
    int T=rand()%N+1;
    if(S.find(T)==S.end())S.insert(T);
    else S.insert(N);
    return S;
}

// F2
unordered_set<int> fun2(int M,int N)
{
    unordered_set<int> S;
    for(int J=N-M+1;J<=N;++J)
    {
        int T=rand()%J+1;
        if(S.find(T)==S.end())S.insert(T);
        else S.insert(J);
    }
    return S;
}

// P
vector<int> f(int N,int M)
{
    vector<int> S;
    for(int J=N-M+1;J<=N;++J)
    {
        int T=rand()%J+1;
        vector<int>::iterator iter=find(S.begin(),S.end(),T);
        if(iter==S.end())S.insert(S.begin(),T);
        else S.insert(iter+1,J);
    }
    return S;
}