Mai intai trebuie sa te autentifici.
Cod sursa(job #2896829)
| Utilizator | Data | 30 aprilie 2022 22:14:06 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 40 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 1.13 kb |
#include <iostream>
#include <fstream>
using namespace std;
#define DIM 2000002
int pi[DIM],n,m,rasp[DIM],r;
string P,T;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void calcul_pi_prefix(){
int k=0;
for(int q=2;q<=m;q++){
while(k>0 && P[k+1]!=P[q])
{
k=pi[q];
}
if(P[k+1]==P[q])
{
k++;
}
pi[q]=k;
}
}
void potrivire_KMP(){
calcul_pi_prefix();
int q=0;
for(int i=1;i<=n;i++)
{
while(q>0 && P[q+1]!=T[i]){
q=pi[q];
}
if(P[q+1]==T[i])
{
q++;
}
if(q==m)
{
rasp[r]=i-m;
r++;
q=pi[q];
}
}
}
int main(){
fin>>P>>T;
P.resize(P.length()+1);
T.resize(T.length()+1);
m=P.length()-1;n=T.length()-1;
for(int i=m;i>=1;i--)
{
P[i]=P[i-1];
}
for(int i=n;i>=1;i--)
{
T[i]=T[i-1];
}
P[0]=' ';T[0]=' ';
potrivire_KMP();
fout<<r<<'\n';
for(int i=0;i<r;i++){
fout<<rasp[i]<<' ';
}
}