Cod sursa(job #2976326)

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

const int N = 2000009;
char a[N], b[N];
int la, lb, 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<la; i++)
	{
		while(c && a[i] != a[c])
			c = t[c-1];
		if(a[i] == a[c])
			c++;
		t[i] = c;
	}	
}
void show()
{
	out<<ct<<endl;
	for(int i=0;i<min(1000,ct);i++)
		out<<p[i]<<' ';
	out<<endl;
}
int main(){
	in>>a>>b;
	la = strlen(a);
	lb = strlen(b);
	build();

	int j=0;
	for(int i=0; i<lb; i++)
	{
		while(j && b[i] != a[j])
			j = t[j-1];
		
		if(b[i] == a[j])
			j++;
			
		if(j == la)
		{
			p[ct++] = i - la + 1;
			j = t[j-1];
		}
	}
	show();
	return 0;
}