prefix_prefixes - CSDN
  • prefix

    2019-07-28 23:36:10
    本题是要求你找出一个组内比原字符串权值大的前缀,而一个组内包含了其他字符串的前缀,但可能也适配于这个字符串。所以说要记录这些前缀的个数才能解出这个问题。 一个方法是用std::map这样的一个红黑树字典,可以...

    本题是要求你找出一个组内比原字符串权值大的前缀,而一个组内包含了其他字符串的前缀,但可能也适配于这个字符串。所以说要记录这些前缀的个数才能解出这个问题。

    一个方法是用std::map这样的一个红黑树字典,可以直接把string类型的前缀出现次数用int/ll类型的数字统计下来。然后再计算各前缀的权值与个数之积,逐一与原字符串权值进行比对,即可得到答案。

    #include <iostream>
    #include <cstdio>
    #include <bits/stdc++.h>
    #include <map>
    #include <algorithm>
    #include <stack>
    #include <iomanip>
    #include <cstring>
    #include <cmath>
    #define DETERMINATION main
    #define lldin(a) scanf_s("%lld", &a)
    #define println(a) printf("%lld\n", a)
    #define reset(a, b) memset(a, b, sizeof(a))
    const int INF = 0x3f3f3f3f;
    using namespace std;
    const double PI = acos(-1);
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    const int mod = 1000000007;
    const int tool_const = 19991126;
    const int tool_const2 = 33;
    inline ll lldcin()
    {
        ll tmp = 0, si = 1;
        char c;
        c = getchar();
        while (c > '9' || c < '0')
        {
            if (c == '-')
                si = -1;
            c = getchar();
        }
        while (c >= '0' && c <= '9')
        {
            tmp = tmp * 10 + c - '0';
            c = getchar();
        }
        return si * tmp;
    }
    ///Untersee Boot IXD2(1942)
    /**Although there will be many obstructs ahead,
    the desire for victory still fills you with determination..**/
    /**Last Remote**/
    string strs[500000];
    ll identify[40],ans[500000];
    ll cost[500000];
    map<string,ll>prefix;//记录前缀出现次数
    int DETERMINATION()
    {
        ios::sync_with_stdio(false);
        cin.tie(0),cout.tie(0);
        ll n,m;
        cin>>n>>m;
        for(int i=1;i<=26;i++)
            cin>>identify[i];
        for(int i=1;i<=n;i++)
            cin>>strs[i];
        for(int i=1; i<=n; i++)
        {
            string tmp="";
            ll tmpr=1;
            for(int j=0; j<strs[i].size(); j++)
            {
                tmp+=strs[i][j];
                prefix[tmp]++;//录入前缀
                tmpr=(tmpr*identify[strs[i][j]-'a'+1])%m;
            }
            cost[i]=tmpr;
        }
        for(int i=1;i<=n;i++)
        {
          string tmp="";
          ll tmpcost=1;
          for(int j=0;j<strs[i].size();j++)
          {
             tmp+=strs[i][j];
             tmpcost=(tmpcost*identify[strs[i][j]-'a'+1])%m;
             if(tmpcost>cost[i])
                ans[i]+=prefix[tmp];
          }
        }
        for(int i=1;i<=n;i++)
            cout<<ans[i]<<" ";
        cout<<endl;
        return 0;
    }
    

    不过既然涉及到前缀,还有一个数据结构可满足需求,即字典树。

    先来简明介绍一下字典树:字典树是一个26叉树,每一个节点对应26个子结点,也就是不同的英文字母。root,根节点不存储任何信息,它的子结点才存储信息,通过从根节点到最底下的子结点的遍历,就可以近似于遍历了一个英文单词或一个前缀。这需要一个二维数组或者一个结构体数组实现。(模板题HDU1251)

    //#include<pch.h>
    #include <iostream>
    #include <cstdio>
    #include <bits/stdc++.h>
    #include <map>
    #include <algorithm>
    #include <stack>
    #include <iomanip>
    #include <cstring>
    #include <cmath>
    #define DETERMINATION main
    #define lldin(a) scanf_s("%lld", &a)
    #define println(a) printf("%lld\n", a)
    #define reset(a, b) memset(a, b, sizeof(a))
    const int INF = 0x3f3f3f3f;
    using namespace std;
    const double PI = acos(-1);
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    const int mod = 1000000007;
    const int tool_const = 19991126;
    const int tool_const2 = 33;
    inline ll lldcin()
    {
        ll tmp = 0, si = 1;
        char c;
        c = getchar();
        while (c > '9' || c < '0')
        {
            if (c == '-')
                si = -1;
            c = getchar();
        }
        while (c >= '0' && c <= '9')
        {
            tmp = tmp * 10 + c - '0';
            c = getchar();
        }
        return si * tmp;
    }
    ///Untersee Boot IXD2(1942)
    /**Although there will be many obstructs ahead,
    the desire for victory still fills you with determination..**/
    /**Last Remote**/
    int trie[1000030][30], sum[1000030];
    ll cnt = 1;
    void ins(char text[])//插入一个单词
    {
        ll root = 1;
        ll lim = strlen(text);
        for (int i = 0; i < lim; i++)
        {
            ll tmp = (text[i] - 'a'+1);
            if (trie[root][tmp] == 0)//如果当前节点没有这个字母对应的子结点,那么创建
                trie[root][tmp] =++cnt;
            sum[trie[root][tmp]]++;//记录从第一个节点到现在的前缀或是单词出现的次数
            root = trie[root][tmp];//迭代搜索
        }
        return;
    }
    ll query(char text[])
    {
        ll root = 1;
        ll lim = strlen(text);
        for (int i = 0; i < lim; i++)
        {
            ll tmp = (text[i] - 'a'+1);
            if (trie[root][tmp] == 0)//没有这样的子结点
                return 0;
            root = trie[root][tmp];
        }
        return sum[root];
    }
    char input[55555];
    int DETERMINATION()
    {
        ios::sync_with_stdio(false);
        cin.tie(0), cout.tie(0);
        while (cin.getline(input,11))//未知数量但已知长度的C++式输入,C可用GETS
        {
            if (input[0] == NULL||strlen(input)==0)
                break;
            else
                ins(input);
        }
        while (cin >> input)
            cout << query(input) << endl;
        return 0;
    }

    而我们恰好可以使用字典树的记录前缀数量的功能来解决这个问题,那么它的查询也就对应着前缀出现的个数。仍然是一番计算就可以解决问题。

    #include<pch.h>
    #include <iostream>
    #include <cstdio>
    #include <bits/stdc++.h>
    #include <map>
    #include <algorithm>
    #include <stack>
    #include <iomanip>
    #include <cstring>
    #include <cmath>
    #define DETERMINATION main
    #define lldin(a) scanf_s("%lld", &a)
    #define println(a) printf("%lld\n", a)
    #define reset(a, b) memset(a, b, sizeof(a))
    const int INF = 0x3f3f3f3f;
    using namespace std;
    const double PI = acos(-1);
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    const int mod = 1000000007;
    const int tool_const = 19991126;
    const int tool_const2 = 33;
    inline ll lldcin()
    {
    	ll tmp = 0, si = 1;
    	char c;
    	c = getchar();
    	while (c > '9' || c < '0')
    	{
    		if (c == '-')
    			si = -1;
    		c = getchar();
    	}
    	while (c >= '0' && c <= '9')
    	{
    		tmp = tmp * 10 + c - '0';
    		c = getchar();
    	}
    	return si * tmp;
    }
    ///Untersee Boot IXD2(1942)
    /**Although there will be many obstructs ahead,
    the desire for victory still fills you with determination..**/
    /**Last Remote**/
    int trie[125000][30], ans[125000],cost[925000],sum[125000],totalcost[125000];
    int identify[30];
    string strs[125000];
    ll cnt = 2;
    void ins(string info,int mod)
    {
    	ll root = 1;
    	for (int i = 0; info[i]; i++)
    	{
    		ll next = (info[i] - 'a' + 1);
    		if (trie[root][next] == 0)
    			trie[root][next] = cnt++;
    		sum[trie[root][next]]++;
    		//ll current = cnt - 1;
    		//if (cnt == 2)
    		//	cost[trie[root][next]] = identify[next] % mod;
    		//else
    		//	cost[trie[root][next]] = (cost[trie[current][next]] * identify[next]) % mod;
    		root = trie[root][next];
    	}
    	return;
    }
    int query(string info,int mod,int index)//查询前缀出现次数
    {
    	ll root = 1;
    	for (int i = 0; info[i]; i++)
    	{
    		ll next = (info[i] - 'a' + 1);
    		if (trie[root][next] == 0)
    			return 0;
    		root = trie[root][next];
    	}
    	//if(info.size()==strs[index].size())
    	//	cout << cost [root]<< endl;
    	//if (cost[root]> totalcost[index])
    		return sum[root];
    	//else
    	//	return 0;
    }
    int DETERMINATION()
    {
    	ios::sync_with_stdio(false);
    	cin.tie(0), cout.tie(0);
    	int n, m;
    	cin >> n >> m;
    	for (int i = 1; i <= 924009; i++)
    		cost[i] = 1;
    	for (int i = 1; i <= 26; i++)
    		cin >> identify[i];
    	for (int i = 1; i <= n; i++)
    	{
    		cin >> strs[i];
    		ins(strs[i],m);
    		ll tmp = 1;
    		for (int j = 0;strs[i][j]; j++)
    		{
    			tmp = (tmp*identify[strs[i][j] - 'a' + 1]) % m;
    		}
    		totalcost[i] = tmp;//计算原字符串权值
    	}
    	//for (int i = 1; i <= n; i++)
    	//	cout << "Total:" << totalcost[i] << endl;
    	for (int i = 1; i <= n; i++)
    	{
    		string tmp = "";
    		ll tmpvalue = 1;
    		for (int j = 0;j<strs[i].size()-1; j++)
    		{
    			tmp += strs[i][j];
    			tmpvalue = (tmpvalue*identify[strs[i][j] - 'a' + 1]) % m;
    			if(tmpvalue>totalcost[i])
    				ans[i] += query(tmp, m, i);//计算
    		}
    	}
    	for (int i = 1; i <= n; i++)
    		cout << ans[i] <<" ";
    	return 0;
    }

     

    展开全文
  • ./configure --prefix

    2018-05-30 17:40:22
    源码的安装一般由3个步骤组成:配置(configure)、编译(make)、安装(make install)...其中--prefix选项是配置安装的路径,如果不配置该选项,安装后可执行文件默认放在/usr /local/bin,库文件默认放在/usr/local/lib...
    源码的安装一般由3个步骤组成:配置(configure)、编译(make)、安装(make install)。

    Configure是一个可执行脚本,它有很多选项,在待安装的源码路径下使用命令./configure –help输出详细的选项列表。

    其中--prefix选项是配置安装的路径,如果不配置该选项,安装后可执行文件默认放在/usr /local/bin,库文件默认放在/usr/local/lib,配置文件默认放在/usr/local/etc,其它的资源文件放在/usr /local/share,比较凌乱。

    如果配置--prefix,如:


    ./configure --prefix=/usr/local/test
    可以把所有资源文件放在/usr/local/test的路径中,不会杂乱。
    用了—prefix选项的另一个好处是卸载软件或移植软件。当某个安装的软件不再需要时,只须简单的删除该安装目录,就可以把软件卸载得干干净净;移植软件只需拷贝整个目录到另外一个机器即可(相同的操作系统)。

    当然要卸载程序,也可以在原来的make目录下用一次make uninstall,但前提是make文件指定过uninstall。


    个人认为,你可以忽略其他的一切,但请把—prefix加上。这里以安装supersparrow-0.0.0为例,我们打算把它安装到目录 /usr/local/supersparrow,于是在supersparrow-0.0.0目录执行带选项的脚本./configure --prefix=/usr/local/supersparrow,执行成功后再编译、安装(make,make install);安装完成将自动生成目录supersparrow,而且该软件所有的文件都被复制到这个目录。为什么要指定这个安装目录?是为了以后的维护方便,如果没有用这个选项,安装过程结束后,该软件所需的软件被复制到不同的系统目录下,很难弄清楚到底复制了那些文件、都复制到哪里去了—基本上是一塌糊涂。

    用了—prefix选项的另一个好处是卸载软件或移植软件。当某个安装的软件不再需要时,只须简单的删除该安装目录,就可以把软件卸载得干干净净;移植软件只需拷贝整个目录到另外一个机器即可(相同的操作系统)。

    一个小选项有这么方便的作用,建议在实际工作中多多使用

    展开全文
  • Linux之 prefix 命令

    2018-10-09 14:31:45
      linux安装软件采用源码安装灵活自由,适用于不同的平台,维护也十分方便。 源码的安装一般由3个步骤组成: 配置(configure) ...具体的安装方法一般作者都会给出文档,这里说明配置(configure...

    摘自 :http://baike.haosou.com/doc/3909580-4103422.html

     

    linux安装软件采用源码安装灵活自由,适用于不同的平台,维护也十分方便。

    源码的安装一般由3个步骤组成:

    配置(configure)

    编译(make)

    安装(make install)

    安装方法:

     

    具体的安装方法一般作者都会给出文档,这里说明配置(configure)的prefix选项

    以安装postgresql-10.0为例,我们打算把他安装到目录 /opt/postgres/db/pgsql, 

    ./configure –prefix=/opt/postgres/db/pgsql

    执行成功后再编译、安装(make,make install);安装完成将自动生成目录/opt/postgres/db/pgsql,而且该软件任何的文档都被复制到这个目录。为什么要指定这个安装目录?是为了以后的维护方便,假如没有用这个选项,安装过程结束后,该软件所需的软件被复制到不同的系统目录下,很难弄清楚到底复制了那些文档、都复制到哪里去了-基本上是一塌糊涂

    用了-prefix选项的另一个好处是卸载软件或移植软件。当某个安装的软件不再需要时,只须简单的删除该安装目录,就能够把软件卸载得干干净净;移植软件只需拷贝整个目录到另外一个机器即可(相同的操作系统)。

    一个小选项有这么方便的作用,建议在实际工作中多多使用。

     

    展开全文
  • 作用就是指定安装路径不指定prefix,则可执行文件默认放在/usr /local/bin,库文件默认放在/usr/local/lib,配置文件默认放在/usr/local/etc。其它的资源文件放在/usr /local/share。你要卸载这个程序,要么在原来的...
    作用就是指定安装路径

    不指定prefix,则可执行文件默认放在/usr /local/bin,库文件默认放在/usr/local/lib,配置文件默认放在/usr/local/etc。其它的资源文件放在/usr /local/share。你要卸载这个程序,要么在原来的make目录下用一次make uninstall(前提是make文件指定过uninstall),要么去上述目录里面把相关的文件一个个手工删掉。
    指定prefix,直接删掉一个文件夹就够了。
    展开全文
  • 源码的安装一般由有这三个步骤:配置(configure)、编译(make)、安装(make install)其中–prefix选项就是配置安装的路径,如果不配置该选项,安装后可执行文件默认放在/usr /local/bin,库文件默认放在/usr/local/lib...
  • 2. 深入了解 prefix

    2012-06-04 19:56:24
    2. 深入了解 prefix 上一页 返回目录 下一页 在 GPI(General-Purpose Instruction)指令里,Legacy Prefix 是在整个编码序列的最前部分,起了对内存操作数进行修饰补充作用。 1. Legacy prefix ...
  • 不指定prefix,则可执行文件默认放在/usr /local/bin,库文件默认放在/usr/local/lib,配置文件默认放在/usr/local/etc。其它的资源文件放在/usr /local/share。你要卸载这个程序,要么在原来的make目录下用一次make...
  • 本来好好的,在自己建的环境里啥啥都装好了,结果更新了一下conda,然后无论是install还是uninstall,都报错,害怕,查了半天没解决,浮然看到github上有老外讲“conda 包仅在 Anaconda 根环境中可用,并非在所有环境...
  • configure--prefix

    2019-08-11 11:15:28
    本文主要说明--prefix参数的作用,其主要用在编译安装源代码应用中的./configure环节。 ./configure --help 查看详细的说明帮助 1、源码安装一般包括几个步骤:配置(configure),编译(make),安装(make ...
  • 一、前缀和(Prefix Sum)定义: 给定一个数组A[1..n],前缀和数组PrefixSum[1..n]定义为:PrefixSum[i] = A[0]+A[1]+...+A[i-1]; 例如:A[5,6,7,8] --> PrefixSum[5,11,18,26] PrefixSum[0] =A[0] ; Prefix...
  • 问题描述 好久之前的一个Android项目,最近需要重构一下 因为Android Studio的开发环境以及...No toolchains found in the NDK toolchains folder for ABI with prefix: mips64el-linux-android 如图所示: ...
  • 一、什么是Trie树Trie树,又叫字典树、前缀树(Prefix Tree)、单词查找树 或 键树,是一种多叉树结构。如下图: 上图是一棵Trie树,表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”,...
  • 场景:在一台服务器上有两个独立项目:管理后台单独一个项目和...上图可以看到:options下面有prefix前缀配置,问题就出在这里,如果直接使用默认的redis操作, 'prefix' => Str::slug(env('APP_NAME', 'lara...
  • tf_prefix的理解

    2017-04-25 18:10:47
    为了支持多个“相似”的机器人,tf使用tf_prefix参数。没有tf_prefix参数,帧名“base_link”将解析为frame_id“/ base_link”。 如果tf_prefix参数设置为“a_tf_prefix”,“base_link”将解析为“/a_tf_...
  • No toolchains found in the NDK toolchains folder for ABI with prefix: mips64el-linux-android" 网上也有解决办法,就是下载旧版的NDK,将其中的toolchain复制到新版的NDK中 但是感觉这种方式,不是解决...
  • ACL和IP prefix-list的区别1:ACL用于匹配路由信息或者数据包的地址,过滤不符合条件的路由信息或数据包;IP Prefix-list不能用于数据包的过滤。2:ACL可以很好匹配路由的前缀部分,但是对于前缀相同而掩码不同的...
  • 标签:prefix.pch究竟是什么?翻阅了一些文章,其实我们可以把它称之为“precompiled header”,从字面上翻译就是预编译头文件,但我们一般叫它为预编译文件!前言:prefix.pch的出现应该追溯到Xcode6以前的版本,在...
  • %@ taglib uri=”http://java.sun.com/jsp/jstl/core” prefix=”c”%&amp;amp;gt; &amp;amp;lt;%@ taglib uri=”http://java.sun.com/jsp/jstl/sql” prefix=”sql”%&amp;amp;gt; 这是因为缺少了...
  • prefix :前缀,当请求匹配前缀时会进行代理 strip-prefix :代理前缀默认会从请求路径中移除,通过该设置关闭移除功能, 当 stripPrefix=true 的时 (会移除) (http://127.0.0.1:8181/api/user/list -> ...
  • 摘要: 前言 升级有风险,参数需谨慎 innodb_large_prefix 关于innodb_large_prefix这个参数,在之前的“MySQL之最”中有提到过,那在5.6和5.7中的表现哪里不一样呢?更直观一点,举个例子: 在5.前言升级有风险,...
1 2 3 4 5 ... 20
收藏数 652,049
精华内容 260,819
关键字:

prefix