Cod sursa(job #3170521)

Utilizator AlexMotoascaMotoasca Alexandru AlexMotoasca Data 17 noiembrie 2023 18:52:26
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <string>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string pattern;
string string1;
int p[2000000001];
void lsp()
{
    int i=2;
    p[0]=-1;
    while(i<string1.size())
    {
        int j=p[i-1];
        while(j>0 && string1[j+1]!=string1[i])
        {
            j=p[j]+1;
        }
        if(string1[j+1]==string1[i])
        {
            j++;
        }
        p[i]=j;
        i++;
    }
}
int nr=0;
int a[2000000001];
void kmp()
{
    int i=1,j=1;
    while(i<=pattern.size())
    {
        while(j>0 && pattern[i]!=string1[j])
        {
            j=p[j-1]+1;
        }
        i++, j++;
        if(j==string1.size())
        {
            a[nr]=i-j;
            nr++;
            j=p[j-1]+1;
        }
    }
}
int main()
{
    cin>>string1;
    cin>>pattern;
    string1='$'+string1;
    pattern='$'+pattern;
    lsp();
    kmp();
    cout<<nr<<endl;
    for(int i=0;i<nr;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}