Pagini recente » Cod sursa (job #1364532) | Cod sursa (job #2322201) | Cod sursa (job #1154054) | Cod sursa (job #402386) | Cod sursa (job #2878066)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string word;
string pattern;
string sir;
vector<int> poz; // pozitiile pe care apare pattern-ul
int lps[4000004];
int n; // n = lungime word
int m; // m = lungime pattern
void compute_lps_1loop()
{
int len = 0;
lps[0] = 0;
int ind = 1;
while(ind < (int)sir.size())
{
if (sir[ind] == sir[len])
{
len++;
ind++;
lps[ind] = len;
}
else // pattern[ind] != pattern[len]
{
if (len > 0) // stiu ca ultimele len caractere corespund cu primele len caractere din pattern
{ // ma uit la urmatorul sufix mai mic care e egal cu prefixul si incerc sa-l lungesc
len = lps[len - 1];
}
else // len e 0 si pattern[ind] != pattern[0] => lps[ind] = 0
{
lps[ind] = 0;
ind++;
}
}
}
}
void kmp()
{
lps[0] = 0;
for (int i = 1; i < (int)sir.size(); i++)
{
int j = lps[i - 1];
while (j > 0 && sir[i] != sir[j])
{
j = lps[j - 1];
}
if (sir[i] == sir[j]) // daca j e 0, atunci lps este 1, altfel daca j != 0
j++;
lps[i] = j;
}
for (int i = m + 1; i < (int)sir.size(); i++)
{
if (lps[i] == m)
{
poz.push_back(i - 2 * m);
}
}
}
int main() {
fin >> pattern >> word;
n = (int)word.size();
m = (int)pattern.size();
sir = pattern + '#' + word;
kmp();
fout << poz.size() << '\n';
for (auto it : poz)
{
fout << it << ' ';
}
return 0;
}