Cod sursa(job #2910808)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 25 iunie 2022 11:01:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda 3_iulie Marime 2.22 kb
#include <cstdio>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <unordered_map>

#define NMAX 2000003
#define DIM 1001

//Solutia cu KMP 
//Compexitate O(n+m)
using namespace std;

FILE* fin, * fout;

char str1[NMAX], str2[NMAX];//cele 2 stringuri in care vrem sa cautam caracterele comune
int prefix[NMAX];//vectorul de prefixe(aici am pastrat indici)
int sol[DIM],nr;
int len1, len2;


int main() {
    fin = fopen("strmatch.in", "r");
    fout = fopen("strmatch.out", "w");

    fgets(str1+1, NMAX, fin);
    fgets(str2+1, NMAX, fin);
   
    len1 = strlen(str1+1);
    if (str1[len1] == '\n') { len1--; };
    len2 = strlen(str2+1);
    if (str2[len2] == '\n') { len2--; };

    int lung = 0;//lungimea celui mai mare prefix care poate fi creat dinamic din primul string
    prefix[1] = 0;
    for (int i = 2; i <= len1; i++)
    {
        while (lung != 0 && str1[i] != str1[lung + 1])
        {
            //ma duc la indicele primului prefix
            lung = prefix[lung];
        }
        if (str1[i] == str1[lung + 1])
        {
            lung++;//cresc lungimea prefixului maxim care poate fi format
        }
        prefix[i] = lung;
    }


    //acum imi testez vectorul de prefixe pe stringul 2(unde vreau sa caut)
    lung = 0;//incep cu lungimea de la 0
    for (int i = 1; i <= len2; i++) {
        while (lung != 0 && str2[i] != str1[lung + 1]) {
            lung = prefix[lung];//ma duc la prefixul initial
        }  
        if (str2[i] == str1[lung + 1])
        {
            lung++;//cresc lungimea pentru ca am gasit un prefix de lungime mai mare
        }
        if (lung == len1)
        {
            //am un prefix de lungimea primului string
            nr++;
            if (nr < DIM)
            {
                sol[nr] = i - len1;
            }
            lung = prefix[lung];//mai micsorez lungimea pentru ca vrem sa cautam si potrivirea urmatoare
        }
    }
    fprintf(fout, "%d\n", nr);
    
    for (int i = 1; i <= min(DIM-1, nr); i++)
    {
        fprintf(fout, "%d ", sol[i]);
    }
        
    return 0;
}