Cod sursa(job #2461577)

Utilizator HumikoPostu Alexandru Humiko Data 25 septembrie 2019 20:50:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cstring>

using namespace std;

//#include <iostream>
#include <fstream>

//ifstream cin ("input.in");
//ofstream cout ("output.out");

ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");

static const int NMAX = 2e6+5;

char s[2*NMAX];
int kmp[2*NMAX];

vector <int> v;
int solve( int n, int targetLen) {
	int ans = 0;

	for ( int i = 2; i <= n; ++i ) {
		kmp[i] = kmp[i-1];

		while ( kmp[i] && s[kmp[i]+1] != s[i] ) {
			kmp[i] = kmp[kmp[i]];
		}

		if ( s[kmp[i]+1] == s[i] ) {
			kmp[i]++;
		}

		if ( kmp[i] == targetLen ) {
			ans++;

			if ( ans > 1000 ) {
				continue;
			}

			v.push_back(i-2*kmp[i]-1);

		}
	}

	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin>>(s+1);
	int n = strlen(s+1);

	s[n+1] = '#';

	cin>>(s+n+2);
	int k = strlen(s+1);

	cout<<solve(k, n)<<'\n';

	for ( auto x:v ) {
		cout<<x<<" ";
	}
}