Cod sursa(job #1503776)

Utilizator PenaluPenalu Ion Penalu Data 16 octombrie 2015 22:23:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <cstring>
#include <map>
#include <unordered_set>
using namespace std;

#define sq 300
#define maxn 100010

string t,s;
int z[4000010], n, m;
vector<int> ans;

void buildZ()
{
	z[0] = 0;
	int l = 0;
	int r = 0;
	for (int i = 1; i < t.length(); ++i)
	{
		if (t[i] != t[0])
			z[i] = 0;
		else
		{
			if (r < i || z[i-l] >= r-i+1)
			{
				z[i] = max(z[i], r-i+1);
				while (i+z[i] < t.length() && t[z[i]] == t[i+z[i]])
					++z[i];
				l = i;
				r = i+z[i]-1;
			}
			else
			{
				z[i] = z[i-l];
			}
		}
		if (i >= n)
		{
			if (z[i] >= n)
				ans.push_back(i-n);
		}
	}
}

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	cin >> t >> s;
	n = t.length();
	m = s.length();
	t += s;
	buildZ();
	cout << ans.size() << "\n";
	for (int i = 0; i < ans.size(); ++i)
		cout << ans[i] << " ";
}