Cod sursa(job #2520621)

Utilizator dream3rDavid Pop dream3r Data 9 ianuarie 2020 15:57:56
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
//#include "pch.h"
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#define min(b) ((b) >(1000) ? (b) : (1000))
using ll = long long int;
using namespace std;
ifstream f("strmatch.in");
ofstream o("strmatch.out");
string a, b;
int n;
int solve;
vector<int> v;
vector<int>poz;
void calcul()
{
	int i = 0;
	int j = 1;
	while (j < a.length())
	{
		if (a[i] == a[j])
		{
			v.push_back(i + 1);
			i++;
			j++;
		}
		else
		{
			v.push_back(0);
			j++;
		}
	}
}

void ans()
{
	int j = 0;// muie neveu
	int i = 0;
	while (i < b.length())
	{
		if (a[j] == b[i])
		{
			j++;
			i++;
		}
		if (j == a.length())
		{
			solve++;
			poz.push_back(i - a.length());
		}
		if (i < b.length() && b[i] != a[j])
		{
			if (j)
			{
				j = v[j - 1];
			}
			else
			{
				i++;
			}
		}
	}
}
int main()
{
	getline(f, a);
	getline(f, b);
	v.push_back(0);
	calcul();
	ans();
	o << solve << "\n";
	for (size_t i = 0; i < min(poz.size()); i++)
	{
		o << poz[i] << " ";
	}

}