Mai intai trebuie sa te autentifici.
Cod sursa(job #2736561)
| Utilizator | Data | 3 aprilie 2021 17:12:19 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 16 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.93 kb |
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int prefix[2000005];
vector <int> ans;
int main()
{
string A, B;
fin >> A >> B;
A = " " + A;
B = " " + B;
int j = 0;
for(int i = 1; i < A.size(); i++)
{
while(A[i] != A[j + 1] && j != 0)
j = prefix[j];
if(A[i] == A[j + 1])
j++;
prefix[i] = j;
}
j = 1;
for(int i = 1; i < B.size(); i++)
{
while(B[i] != A[j] && j != 1)
j = prefix[j - 1];
if(B[i] == A[j])
j++;
if(j == A.size())
{
ans.push_back(i - A.size() + 1);
j = prefix[j - 1];
}
}
fout << ans.size() << '\n';
for(int i = 0; i < min(1000, (int)ans.size()); i++)
fout << ans[i] << ' ';
return 0;
}
