Cod sursa(job #1988876)

Utilizator Alex18maiAlex Enache Alex18mai Data 4 iunie 2017 23:58:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

char sir[2000010];
int p[2000010];
int pos[2000010];

int main()
{
    cin>>(sir+1);
    int lone=strlen(sir+1);
    sir[lone+1]='#';
    cin>>(sir+lone+2);
    int ltwo=strlen(sir+1);
    int s=0;
    for (int i=2; i<=ltwo; i++){
        int x=p[i-1];
        while(sir[x+1]!=sir[i] && x!=0){
            x=p[x];
        }
        if (sir[x+1]==sir[i]){
            p[i]=x+1;
            if (p[i]==lone){
                s++;
                pos[s]=i-lone-lone-1;
            }
        }
    }
    cout<<s<<'\n';
    if (s>=1000){
        s=1000;
    }
    for (int i=1; i<=s; i++){
        cout<<pos[i]<<" ";
    }
    return 0;
}