Cod sursa(job #2560311)

Utilizator serafimalex2001Serafim Alex serafimalex2001 Data 27 februarie 2020 21:32:11
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

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

char s[2000009];
char t[2000009];
int n,m;
int pref[2000009];

void Read()
{
    int i,j = 0;
    fin>>s;
    fin>>t;
    m = strlen(s);
    n = strlen(t);
    for(int i = 1; i < m; )
    {
        if(s[i] == s[j])
        {
            pref[i] = j+1;
            ++i;
            ++j;
        }
        else
        {
            if(j != 0)
            {
                j = pref[j-1];
            }
            else
            {
                pref[i] = 0;
                ++i;
            }
        }
    }
}

void Do()
{
    int ct = 0;
    int sol[1005];
    int i,j = 0;
    i = 0;
    while( i < n)
    {
        if(t[i] == s[j])
        {
            ++i;
            ++j;
        }
        if( j == m)
        {
            sol[++ct] = i-j;
            j = pref[j-1];
            if(ct > 1000)
                break;
        }
        else if(i < n && s[j] != t[i])
             {
                 if(j!=0)
                    j = pref[j-1];
                else ++i;
             }
    }
    fout<<ct<<"\n";
    for(i=1; i<=ct; ++i)
        fout<<sol[i]<<" ";
}

int main()
{
    Read();
    Do();
    return 0;
}