Cod sursa(job #1810839)

Utilizator ZeratulVeress Szilard Zeratul Data 20 noiembrie 2016 16:55:39
Problema Potrivirea sirurilor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

int p[2000000],mereti,meretj;
string text,s;
int counter, solve[1001];

void create_temporary_array(string s,int p[])
{
    int j = 0, i = 1, meret = s.size();
    while(i < meret)
    {
        if(s[j] == s[i])
        {
            p[i] = j + 1;
            i++;
            j++;
        }

        else
        {
            while(j != 0 and s[j] != s[i])
            {
                j = p[j-1];
            }
            p[i] = j + (s[j] == s[i]);
            i++;
        }
    }
}

int main()
{
    ifstream be("strmatch.in");
    ofstream ki("strmatch.out");
    getline(be,s);
    getline(be,text);
    create_temporary_array(s,p);
    mereti = text.size();
    meretj = s.size();
    int i = 0, j = 0;

   /* for(int i = 0;i < s.size();i++)
    {
        ki<<p[i]<<" ";
    }*/

    while( i < mereti)
    {
        if(text[i] == s[j])
        {
            i++;
            j++;
        }
        else
        {
            if(j == 0)
            {
                i++;
            }
            j = p[j-1];
        }
        if(j == meretj)
        {
            if(counter < 1000)
                solve[counter] = i - j;
            counter++;
            j = p[j-1];
        }
    }

    ki<<counter<<endl;
    short woohoo = min(1000,counter);
    for(int i = 0;i<woohoo;i++)
    {
        ki<<solve[i]<<" ";
    }

    return 0;
}