Cod sursa(job #3175743)
| Utilizator | Data | 26 noiembrie 2023 13:16:45 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 40 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 1.2 kb |
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MOD 666013
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int pi[2000001];
char a[2000001];
char b[2000001];
int main()
{
fin >> a >> b;
pi[0]=0;
int len=0;
int i=1;
while(i < strlen(a))
{
if(a[i]==a[len])
{
len++;
pi[i]=len;
i++;
}
else
{
if(len !=0)
{
len = pi[len-1];
}
else
{
pi[i]=0;
i++;
}
}
}
vector<int> r;
i=0;
int j=0;
while(i<strlen(b))
{
if(a[j]==b[i])
{
j++;
i++;
}
if(j==strlen(a))
{
r.push_back(i-j);
j=pi[j-1];
}
else if(i < strlen(b) && a[j]!=b[i])
{
if(j!=0)
{
j = pi[j-1];
}
else
{
i++;
}
}
}
fout << r.size() << "\n";
for(int i : r)fout << i << " ";
}
