Cod sursa(job #2470444)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 9 octombrie 2019 10:56:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x)) 
    
using namespace std;

const int MAXN = (int) 2e6;

char a[2 * MAXN + 1], b[MAXN + 1];
int z[2 * MAXN + 1];
   
int main() {
#if 1
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
#endif
    int i;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
	
	cin >> a + 1 >> b;
	int n = strlen(a + 1), m = strlen(b);
	for(i = 0; i < m; i++) {
		a[i + n + 1] = b[i];
	}
	
	z[1] = n + m;
	int pos = 0;
	for(i = 2; i <= n + m; i++) {
		if(pos + z[pos] >= i) {
			z[i] = min(pos + z[pos] - i, z[i - pos + 1]);
		}
		while(i + z[i] <= n + m && a[i + z[i]] == a[z[i] + 1]) {
			z[i]++;
		}
		if(pos + z[pos] < i + z[i]) {
			pos = i;
		}
	}

	vector <int> sol;
	int ans = 0;
	for(i = n + 1; i <= n + m; i++) {
		if(z[i] >= n) {
			ans++;
			if(sol.size() < 1000) {
				sol.push_back(i - n - 1);
			}
		}
	}
	cout << ans << "\n";
	for(auto it : sol) {
		cout << it << " ";
	}
	return 0;
}