数据结构上机复习二

1.KMP

#include <iostream>
#include <string>
using namespace std;
const int N=1e5+10;
void buildnext(string p,int next[])
{
    int m=p.size();
    int k=next[0]=-1;
    for(int j=0;j+1<m;j++)
    {
        while(k!=-1&&p[k]!=p[j])
            k=next[k];
        next[j+1]=++k;
    }
}
int KMP(string s,string p)
{
    int n=s.size(),m=p.size();
    int next[N];
    buildnext(p,next);
    int i=0,j=0;
    while(i<n&&j<m)
    {
        if(j==-1||s[i]==p[j])
        {
            i++,j++;
        }
        else
            j=next[j];
    }
    printf("%d %d %d \n",next[m/4],next[m*2/4],next[3*m/4]);
    return j==m?i-m:-1;
}
int main()
{
    string s,p;
    cin>>s>>p;
    int x=KMP(s,p);
    cout<<x;
}

2.好前缀

#include <iostream>
#include <string>
using namespace std;

const int N = 1e5 + 10;
void buildnext(int next[], string p)
{
	int k = next[0] = -1;
	int m = p.size();
	for (int j = 0; j + 1 <= m; j++)
	{
		while (k != -1 && p[k] != p[j])
			k = next[k];
		next[j + 1] = ++k;
	}
}
int main()
{
	string p;
	cin >> p;
	int m = p.size();
	int next[N];
	buildnext(next, p);
	int maxn = 0;
	for (int j = 0; j < m; j++)
	{
		if (next[j] > maxn)
			maxn = next[j];
	}
	cout << maxn << endl;
}

3.edgnb

#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 10;

void buildnext(int next[], string p)
{
	int k = next[0] = -1;
	int m = p.size();
	for (int j = 0; j+1 <= m; j++)
	{
		while (k != -1 && p[k] != p[j])
			k = next[k];
		next[j + 1] = ++k;
	}
}
int KMP(string s, string p)
{
	int n = s.size();
	int m = p.size();
	int next[N];
	buildnext(next, p);
	int i = 0, j = 0;
	int cnt = 0;
	while (i < n && j < m)
	{
		if (j == -1 || s[i] == p[j])
			i++, j++;
		else
			j = next[j];
		if (j == m)
		{
			cnt++;
			j = next[j];
		}
	}
	return cnt;
}
int main()
{
	int t;
	cin >> t;
	string e = "edgnb";
	while (t--)
	{
		string s;
		cin >> s;
		int k;
		cin >> k;
		string p = e;
		for (int i = 0; i < k - 1; i++)
			p += e;
		int cnt = KMP(s, p);
		cout << cnt << endl;
	}
}

4.艾迪的编码算法

#include <iostream>
#include <string>
#include <cstring>;
using namespace std;
const int N = 1e5 + 10;
const int M = 200;
int lastloc[M];
int num[N];
int exist[N];
int main()
{
	string s;
	cin >> s;
	memset(lastloc, 0, sizeof lastloc);
	memset(num, 0, sizeof num);
	memset(exist, 0, sizeof exist);
	int n = s.size();
	for (int i = 0; i < n; i++)//确定每个字符最后出现的位置
		lastloc[s[i]] = i;
	for (int i = n - 1; i > 0; i--)//从后往前，记录每个位置后面不重复字母的个数
	{
		if (exist[s[i]] == 0)
		{
			exist[s[i]] = 1;
			num[i - 1] = num[i] + 1;
		}
		else
			num[i - 1] = num[i];
	}

	for (int i = 0; i < n; i++)
	{
		s[i] = 'a' + num[lastloc[s[i]]];
	}
	cout << s;
}

5.计算中值表达式

#include <iostream>
#include <stack>
#include <string>
using namespace std;
const int M = 200;
const int INF = 0x3f;
int quick_pow(int x, int y)
{
	if (y == 0) return 1;
	else if (y % 2 == 0) return quick_pow(x * x, y / 2);
	else return quick_pow(x * x, y / 2) * x;
}

bool operation(stack<int>&NUM, stack<char>&OP)
{
	int b = NUM.top();
	NUM.pop();
	int a = NUM.top();
	NUM.pop();
	char op = OP.top();
	OP.pop();
	if (op == '+')
		NUM.push(a + b);
	else if (op == '-')
		NUM.push(a - b);
	else if (op == '*')
		NUM.push(a * b);
	else if (op == '/')
	{
		if (b == 0) return false;
		NUM.push(a / b);
	}
	else
		NUM.push(quick_pow(a, b));
	return true;
}
int cal(stack<int>&NUM, stack<char>&OP,string s)
{
	int p[M];
	p['+'] = p['-'] = 1;
	p['*'] = p['/'] = 2;
	p['^'] = 3;
	int n = s.size();
	for (int i = 0; i < n; i++)
	{
		if (s[i] >= '0' && s[i] <= '9')
		{
			int tmp = 0;
			while (s[i] >= '0' && s[i] <= '9')
				tmp = 10 * tmp + s[i++] - '0';
			i--;
			NUM.push(tmp);
		}
		else if (s[i] == '(')
			OP.push('(');
		else if (s[i] == ')')
		{
			while (OP.top() != '(')
			{
				bool sign=operation(NUM, OP);
				if (sign == 0) return INF;
			}
			OP.pop();
		}
		else
		{
			while (!OP.empty() && OP.top() != '(' && p[s[i]] <= p[OP.top()])
			{
				bool sign = operation(NUM, OP);
				if (sign == 0) return INF;
			}
			OP.push(s[i]);
		}
	}
	while (!OP.empty())
	{
		bool sign = operation(NUM, OP);
		if (sign == 0) return INF;
	}
	return NUM.top();
}
int main()
{
	string s;
	while (cin >> s)
	{
		int n = s.size();
		stack<int>NUM;
		stack<char>OP;
		int ans = cal(NUM, OP, s);
		if (ans == INF)
			cout << "INVALID" << endl;
		else
			cout << ans << endl;
	}
	return 0;
}

6.字母游戏

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;

void buildnext(int next[],string p)
{
	int m = p.size();
	int k = next[0] = -1;
	for (int j = 0; j + 1 <= m; j++)
	{
		while (k != -1 && p[k] != p[j])
			k = next[k];
		next[j + 1] = ++k;
	}
}

int main()
{
	string s;
	while (cin >> s)
	{
		int next[N];
		int n = s.size();
		reverse(s.begin(), s.end());
		buildnext(next, s);
		int maxn = 0;//记录S中最长重复后缀
		for (int i = 0; i <= n; i++)
		{
			if (next[i] > maxn)
				maxn = next[i];
		}
		//寻找第二长相等前后缀
		if (next[n] == -1) next[next[n]] = 0;
		else if (next[next[n]] == -1) next[next[n]] = 0;
		int qlen = n - 2 * next[next[n]];
		if (qlen < 0)
			qlen = 0;
		int x = maxn + qlen;
		printf("plen:%d  qlen:%d  x:%d\n", maxn, qlen, x);
	}
}

7.小龙猜数字

#include <iostream>
#include <string>
using namespace std;
const int N = 1e4 + 10;
void buildnext(int next[], string p)
{
	int m = p.size();
	int k = next[0] = -1;
	for (int j = 0; j + 1 <= m; j++)
	{
		while (k != -1 && p[k] != p[j])
			k = next[k];
		next[j + 1] = ++k;
	}
	for (int j = 1; j <= m; j++)
	{
		if (next[j] == 0) continue;
		while (next[next[j]] != 0)
			next[j] = next[next[j]];
	}
}
int main()
{
	int n;
	string s;
	cin >> n >> s;
	int next[N];
	buildnext(next, s);
	int sum = 0;
	for (int i = 1; i <= n; i++)
	{
		if(next[i]!=0)
			sum += i-next[i];
	}
	cout << sum;
}