Cod sursa(job #1881818)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 16 februarie 2017 19:10:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0);
#define tie cin.tie(0);
#define mp make_pair
#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define zeros(x) ( (x ^ (x - 1)) & x )
  
using namespace std;
 
int n, v[2000100];
string s, S;
vector < int > V;

void prefix()
{
	int i = 0;
	for (int j = 1; j < s.size();)
	{
		if (s[i] == s[j])
		{
			v[j] = i + 1;
			i++, j++;
		}else
		{
			if (i != 0)
				i = v[i - 1];
			else
				v[j] = 0, j++;
		}
	}
}

void solve()
{
	int i = 0, j = 0;
	while (i < S.size())
	{
		if (S[i] == s[j]) i++, j++;
		else if (j != 0) j = v[j - 1];
				else i++;
		if (j == s.size()) V.push_back(i - j);
	}
}

int main(){
    IOS tie
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    cin >> s;
    cin >> S;
    prefix();
    solve();
    cout << V.size() << "\n";
    int sz = V.size();
    for (int i = 0; i < min(sz, 1000); i++)
		cout << V[i] << " ";
    cerr << "Fucking time elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}