Cod sursa(job #3212352)

Utilizator cosmin395dimofte cosmin cosmin395 Data 11 martie 2024 16:59:51
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int p[2000005];
string s1,s2;
vector <int> v;
void precalc(string s)
{
    p[0]=0;
    for(int i=1;i<s.size();i++)
    {
        int k=0;
        while(s[k]==s[i+k] && i+k<s.size())
            k++;
        p[i]=k;
    }
}
void afis()
{
    int nr=0;
    for(int i=0;i<s2.size();i++)
    {
        int k=0;
        while(s1[k]==s2[i+k] && k<s1.size() && i+k<=s2.size())
            k++;
        if(k==s1.size())
        {
            nr++;
            v.push_back(i);
        }
        else
            i+=p[k];
    }
    cout<<nr<<'\n';
    for(auto x:v)
        cout<<x<<' ';

}
int main()
{

    cin>>s1;
    precalc(s1);
    cin>>s2;
    afis();
    return 0;
}