Cod sursa(job #2976312)

Utilizator dumitrache12Dumitrache Iulian dumitrache12 Data 8 februarie 2023 22:19:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include<bits/stdc++.h>
using namespace std;

const int N = 2000009;
char a[N], b[N];
int t[N], p[N], ct;

ifstream in ("strmatch.in");
ofstream out("strmatch.out");
// auto& in = cin;
// auto& out = cout;

void build()
{
	int c = 0;
	for(int i = 1; i<strlen(a); i++)
	{
		while(c && a[i] != a[c])
			c = t[c-1];
		if(a[i] == a[c])
			c++;
		t[i] = c;
	}
		
}
void debug_t()
{
	for(int i = 0; i<strlen(a); i++)
		out<<t[i]<<' ';
	out<<endl;
}
void show()
{
	out<<ct<<endl;
	for(int i=0;i<ct;i++)
		out<<p[i]<<' ';
	out<<endl;
}
int main(){
	in>>a>>b;
	build();
	// debug_t();

	int j=0;
	for(int i=0; i<strlen(b); i++)
	{
		// out<<"i: "<<i<<"; j: "<<j<<endl;
		while(j && b[i] != a[j])
			j = t[j-1];
		
		if(b[i] == a[j])
			j++;
			
		if(j == strlen(a))
		{
			// out<<"found"<<endl;
			p[ct++] = i - strlen(a) + 1;
			j = t[j-1];
		}
	}
	show();
	return 0;
}