Cod sursa(job #1316475)

Utilizator GrandmasterSoucup Bogdan Grandmaster Data 13 ianuarie 2015 20:51:21
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <utility>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <limits>
#include <sstream>
#include <deque>
#include <bitset>
#include <complex>
#include <functional>
#include <memory>
#include <numeric>
#define x first
#define y second
typedef std::pair<int, int> pii;

using namespace std;



int main () {
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");
	char s[2000007], g[2000007];
	fin.get(s, 2000007);
	fin.get();
	fin.get(g, 2000007);
	int n = strlen(s);
	int m = strlen(g);
	int k = 0;
	int pi[200000], please[200000], volc = 0;
	long long meg = 0;
	pi[1] = 0;
	for(int i = 2; i < n; i++)
	{
		while(k > 0 && (s[k + 1]) != s[i])
			k = pi[k];
		if(s[k + 1] == s[i])
			k++;
		pi[i] = k;
	}
	int q = 0;
	for(int i = 1; i < m; i++)
	{
		while(q > 0 && (s[q + 1] != g[i]))
			q = pi[q];
		if(s[q + 1] == g[i])
			q++;
		if(q == n - 1)
		{
			volc++;
			please[meg++] = i - n + 1;
		}
	}
	if(volc >= 1000)
	{
		fout << volc << "\n";
		for(int i = 0; i < 1000; i++)
			fout << please[i] << " ";
	}
	else
	{
		fout << volc << "\n";
		for(int i = 0; i < volc; i++)
			fout << please[i] << " ";
	}
	return 0;
}