Cod sursa(job #2851342)

Utilizator Catalin2002Catalin Craciun Catalin2002 Data 18 februarie 2022 14:29:16
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <list>
using namespace std;

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

list <int> l;


char a[1000000];
int v[1000000];

int main() {

    char c;

    int i = 0,j=0;
    fin.get(a[i]);

    while (a[i]!='\n'){

        i++;
        fin.get(a[i]);

        if(a[i]==a[j])
            v[i]=++j;
        else{

            while(j!=0 && a[i]!=a[j] )
                j=v[j];

            if(a[i]==a[j])
                v[i]=++j;
            else
                v[i]=0;
        }

    }

    int ct=0, n=i, poz=0;
    i=0;
    while (c!='\n' && !fin.eof()){

        fin.get(c);


        if(a[i] == c)
            i++;
        else
            i = v[i];

        if(i == n){
            ct++;
            if(ct <= 1000)
                l.push_back(poz-i+1);

            i = v[i-1];
        }

        poz++;
    }

    fout<<ct<<"\n";

    _List_iterator<int> it;
    for(it = l.begin(); it != l.end(); it++)
        fout<<(*it)<<" ";




    return 0;
}