What is the basis for Melisandre's belief that Stannis is Azor Ahai?

Question

As the title states, why does Melisandre believe that Stannis is Azor Ahai?

Because he wields a shining sword? Thoros of Myr swings a burning sword at tournaments...
The sword was even created by her own ceremony at Dragonstone and given to Stannis. This ceremony also provided the smoke and salt. A ceremony everyone could create by burning septs and plunging a sword in one of them, not exclusive to Stannis really. Did I miss something? I've looked at Is the Red Woman confusing Stannis for Daenerys? but the answers there doesn't really explain her original belief.

She creates all the signs of Azor Ahai herself and although she may be ambitious and can misread signs, something must have sparked the original belief that Stannis is him.

Answers from book canon with some logic speculation is accepted.

Answer 1

She believes Stannis is Azor Ahai because she has seen it in her flames (believes she has, at least) and because she interpreted an ancient prophecy to mean it was him. In aSoS, Davos III, she tells Davos:

He is the Lord's chosen, the warrior of fire. I have seen him leading the fight against the dark, I have seen it in the flames. [...] It is written in prophecy as well. When the red star bleeds and the darkness gathers, Azor Ahai shall be born amidst smoke and salt to wake dragons out of stone. The bleeding star has come and gone, and Dragonstone is the place of smoke and salt. Stannis Baratheon is Azor Ahai reborn!

Her interpretation of the prophecy has logic behind it - Dragonstone is an island in the middle of the sea (salt) and it also has volcanic activity (there's smoke coming from the crater). There's a stone castle there with towers and turrets shaped like dragons (dragons out of stone). In addition, at the time he lays claim to the Iron Throne there's a red comet in the sky (the red star bleeds) and the White Walkers start marching (presumably Melisandre has seen that in her flames), therefore darkness gathers.

Answer 2

The Prince That Was Promised needs to be a Targaryen. Assuming that Azor Ahai Reborn and The Prince That Was Promised are the same person (disputed), this would mean that Azor Ahai Reborn must be a Targaryen. She only knows of four living Targaryens at that point:

1. Daenerys Targaryen.
2. Renly Baratheon.
3. Stannis Baratheon.
4. Maester Aemon.

We may know now that Jon Snow is a Targaryen, but she presumably did not know that then.

Some speculate that Tyrion is actually the bastard child of Aerys II, making him a half brother of Daenerys. That would explain why Tywin was so adamant that Tyrion not inherit Casterly Rock.

Maester Aemon is old and hardly anyone's idea of a princely hero.

The original Azor Ahai was a man, so it seems likely that the reborn one would be as well. That would leave out Daenerys. Note that the word used for Prince was the same as the word for Princess, so we can't go by the translated title.

In addition to that, as already posted, she had seen Stannis in her visions, not Renly.