Cod sursa(job #2741674)

Utilizator MarcGrecMarc Grec MarcGrec Data 17 aprilie 2021 16:00:07
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#define MAX_L 2000000

#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char A[MAX_L + 1], B[MAX_L + 1];
int FA[1 << 8], ma, F[1 << 8], m;
int cnt;
vector<int> I;

int main()
{
	fin >> A >> B;
	
	const int a = (int) strlen(A);
	
	for (int i = 0; i < a; ++i)
	{
		const int elem = A[i];
		
		++FA[elem];
		
		if (FA[elem] == 1)
		{
			++ma;
		}
	}
	
	for (int i = 0; B[i] != '\0'; ++i)
	{
		int elem = B[i];
		
		{
			const int tempF = F[elem];
			++F[elem];
			
			if (tempF == FA[elem])
			{
				--m;
			}
			else
			{
				if (FA[elem] == F[elem])
				{
					++m;
				}
			}
		}
		
		if ((i - a + 1) >= 0)
		{
			if ((i - a) >= 0)
			{
				elem = B[i - a];
				
				{
					const int tempF = F[elem];
					--F[elem];
					
					if (tempF == FA[elem])
					{
						--m;
					}
					else
					{
						if (FA[elem] == F[elem])
						{
							++m;
						}
					}
				}
			}
			
			if ((m == ma) && (strncmp(A, B + i - a + 1, a) == 0))
			{
				++cnt;
				
				if (I.size() < 1000)
				{
					I.push_back(i - a + 1);
				}
			}
		}
	}
	
	fout << cnt << '\n';
	
	for (int elem : I)
	{
		fout << elem << ' ';
	}
	
    fin.close();
    fout.close();
    return 0;
}