Cod sursa(job #2430070)

Utilizator rd211Dinucu David rd211 Data 12 iunie 2019 17:01:43
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char str[2000010],pattern[2000010];
int helper[2000010];
int found[2000010],indexFound;
int m,n;
void buildHelper()
{
    for(int i = 1,j=0;i<=m;)
    {
        if(pattern[i]==pattern[j])
        {
            helper[i]=j+1;
            i++;
            j++;
        }
        else
        {
            if(j!=0)
                j = helper[j-1];
            else
                i++;
        }
    }
}
void searchStr()
{
    for(int i = 0,j = 0;i<=n;)
    {
        if(str[i]==pattern[j])
        {
            if(j==m)
                found[indexFound++]=i-m;
            j++,i++;
        }
        else
        {
            if(j!=0)
                j = helper[j-1];
            else
                i++;
        }
    }
}
int main()
{
    fin>>pattern>>str;
    int i;
    for(i = 0;pattern[i]!='\0';i++);
    m = i-1;
    for(i = 0;str[i]!='\0';i++);
    n = i-1;
    buildHelper();
    searchStr();
    cout<<indexFound<<endl;
    if(indexFound>1000)
        indexFound=1000;
    for(int i = 0;i<indexFound;i++)
    {
        cout<<found[i]<<" ";
    }
    return 0;
}